CF771F.Bear and Isomorphic Points

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Bearland is a big square on the plane. It contains all points with coordinates not exceeding 10610^{6} by the absolute value.

There are nn houses in Bearland. The ii -th of them is located at the point (xi,yi)(x_{i},y_{i}) . The nn points are distinct, but some subsets of them may be collinear.

Bear Limak lives in the first house. He wants to destroy his house and build a new one somewhere in Bearland.

Bears don't like big changes. For every three points (houses) pip_{i} , pjp_{j} and pkp_{k} , the sign of their cross product (pjpi)×(pkpi)(p_{j}-p_{i})×(p_{k}-p_{i}) should be the same before and after the relocation. If it was negative/positive/zero, it should still be negative/positive/zero respectively. This condition should be satisfied for all triples of indices (i,j,k)(i,j,k) , possibly equal to each other or different than 11 . Additionally, Limak isn't allowed to build the house at the point where some other house already exists (but it can be the point where his old house was).

In the formula above, we define the difference and the cross product of points (ax,ay)(a_{x},a_{y}) and (bx,by)(b_{x},b_{y}) as:

(ax,ay)(bx,by)=(axbx,ayby),(a_{x},a_{y})-(b_{x},b_{y})=(a_{x}-b_{x},a_{y}-b_{y}), (ax,ay)×(bx,by)=axbyaybx.(a_{x},a_{y})×(b_{x},b_{y})=a_{x}·b_{y}-a_{y}·b_{x}. Consider a set of possible new placements of Limak's house. Your task is to find the area of that set of points.

Formally, let's say that Limak chooses the new placement randomly (each coordinate is chosen independently uniformly at random from the interval [106,106][-10^{6},10^{6}] ). Let pp denote the probability of getting the allowed placement of new house. Let SS denote the area of Bearland ( S=41012S=4·10^{12} ). Your task is to find pSp·S .

输入格式

The first line of the input contains an integer TT ( 1<=T<=5001<=T<=500 ) — the number of test cases. The description of the test cases follows.

The first line of the description of a test case contains an integer nn ( 3<=n<=2000003<=n<=200000 ) — the number of houses.

The ii -th of the next nn lines contains two integers xix_{i} and yiy_{i} ( 106<=xi,yi<=106-10^{6}<=x_{i},y_{i}<=10^{6} ) — coordinates of the ii -th house. No two houses are located at the same point in the same test case. Limak lives in the first house.

The sum of nn won't exceed 200000200000 .

输出格式

Print one real value, denoting the area of the set of points that are possible new placements of Limak's house.

Your answer will be considered correct if its absolute or relative error doesn't exceed 10610^{-6} . More precisely, let the jury's answer be bb , and your answer be aa . Then your answer will be accepted if and only if .

输入输出样例

  • 输入#1

    4
    4
    5 3
    0 1
    10 1
    3 51
    3
    -999123 700000
    -950000 123456
    -950000 987654
    3
    2 3
    10 -1
    -4 6
    5
    1 3
    5 2
    6 1
    4 4
    -3 3
    

    输出#1

    250.000000000000
    100000000000.000000000000
    0.000000000000
    6.562500000000
    

说明/提示

In the sample test, there are 44 test cases.

In the first test case, there are four houses and Limak's one is in (5,3)(5,3) . The set of valid new placements form a triangle with vertices in points (0,1)(0,1) , (10,1)(10,1) and (3,51)(3,51) , without its sides. The area of such a triangle is 250250 .

In the second test case, the set of valid new placements form a rectangle of width 5000050000 and height 20000002000000 . Don't forget that the new placement must be inside the big square that represents Bearland.

In the third test case, the three given points are collinear. Each cross product is equal to 00 and it should be 00 after the relocation as well. Hence, Limak's new house must lie on the line that goes through the given points. Since it must also be inside the big square, new possible placements are limited to some segment (excluding the two points where the other houses are). The area of any segment is 00 .

首页