Bear and Isomorphic Points
Contest: VK Cup 2017 - Round 1
Difficulty rating: 3300
Tags: geometry, two pointers

Bearland is a big square on the plane. It contains all points with coordinates not exceeding 106 by the absolute value.

There are n houses in Bearland. The i-th of them is located at the point (xi, yi). The n 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) pi, pj and pk, the sign of their cross product (pj - pi) × (pk - pi) 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), possibly equal to each other or different than 1. 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) and (bx, by) as:

(ax, ay) - (bx, by) = (ax - bx, ay - by),

(ax, ay) × (bx, by) = ax·by - ay·bx.

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]). Let p denote the probability of getting the allowed placement of new house. Let S denote the area of Bearland (S = 4·1012). Your task is to find p·S.

Input format:
The first line of the input contains an integer T (1 ≤ 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 n (3 ≤ n ≤ 200 000) — the number of houses.

The i-th of the next n lines contains two integers xi and yi ( - 106 ≤ xi, yi ≤ 106) — coordinates of the i-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 n won't exceed 200 000.

Output format:
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 10 - 6. More precisely, let the jury's answer be b, and your answer be a. Then your answer will be accepted if and only if $$\frac{|a-b|}{\max(1,b)} \leq 10^{-6}$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the sample test, there are 4 test cases.

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

In the second test case, the set of valid new placements form a rectangle of width 50 000 and height 2 000 000. 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 0 and it should be 0 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 0.

Example input:
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

Example output:
250.000000000000
100000000000.000000000000
0.000000000000
6.562500000000

Editorial:
If p1 is collinear with some two other points, we should print 0. Now let's assume that no two points are collinear with p1.
The naive solution is to iterate over O(n2) pairs of points. For each pair of points there is a line going through them both, and we know that the new placement of p1 should be on the same side (e.g. on the left) from the line - otherwise the sign of the cross product will change. In other words, the new placement must belong to some halfplane. What we're looking for is the intersection of those O(n2) halfplanes, what can be found in $$O(n^2 \log n)$$. We should also remember that the new placement must be inside the big square, what can be achieved by adding four halfplanes (each for one side of the square).
It turns out that it's quite easy to improve the complexity of the naive solution. Let's first sort other n - 1 points by angle. One way to approach the problem is to think "we are interested in those new placements that don't affect the sorting of those n - 1 points" - this is almost enough to get the intended solution. If sorted (in the clockwise order) points are p2, p3, ..., pn, taking into account a halfplane that goes through points pi and pi + 1 ensures that pi + 1 is further in the clockwise order than pi (i.e. it is more "on the right" if we look from p1). Usually, pi + 2 is also more "on the right" than pi, and so on, till some point pj that is no longer "on the left" from pi (if we look from p1). For each i, let's find the first j that pj is "on the left" from pi (move indices i and j with two pointers) and then consider a halfplane that goes through pi and pj. To sum up, we consider n halfplanes determined by pairs (pi, pi + 1) and n halfplanes determined by pairs (pi, pj) where pi and pj are almost opposite to each other, with respect to p1. It turns out that this is already a working solution - no other halfplanes are needed. The answer is the intersection of found O(n) halfplanes. Let's prove the correctness.
Let's assume that one of halfplanes (going through some pa and pb) wasn't considered, while it should be because it would affect the answer. And let's say that pb is more "on the right" than pa, and a < b. If |a - b| = 1, we surely considered that halfplane. Otherwise, if there is some other point with index $$m \in [a+1,b-1]$$ such that it is on the proper side of the line (pa, pb), i.e. on the same side as p1, halfplanes determined by pairs (a, m) and (m, b) completely cover that (a, b) halfplane. Here we must use induction: if each halfplane determined by a pair (a, b) for smaller value of b - a is either taken or covered by some other taken halfplanes, then also halfplanes with greater differences b - a will be considered (remember that we assumed that there is some other points with index $$m \in [a+1,b-1]$$ such that ...).
The case analysed above is shown on the drawing below. Let R denote the red point. If halfplanes (pa, R) and (R, pb) are considered (or from induction they are covered by something else), we don't need considering (pa, pb).
What remains is the case when a + 1 ≠ b and each point with index in [a + 1, b - 1] is on the line (pa, pb) or on the wrong side (not the same as p1). It quite easily implies that our line is already covered everywhere except for the segment (pa, pb), see the drawing:
Now we should take a look at points pb + 1, pb + 2, .... If one of them pk is on the wrong side of the line (pa, pb) (i.e. on the side different than p1), the halfplane (pk - 1, pk) covers our segment (pa, pb) and we are done. Otherwise, all those points are on the proper side (the same as p1). Eventually one of them will be the last one that is "on the right" from pa and let's remember that we consider halfplanes determined by such pairs (earlier denoted as pi and pj). Since that point is on the proper side of the line (pa, pb), the segment is covered: