Defend the Recipe

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef holds all his secret recipes inside his house. For this reason, Chef's house is closed off by walls, thus it is very secure. You can think of the walls as a simple polygon in the 2D plane, and you can consider the thickness of the walls to be negligible, i.e., 0.
Unfortunately, bad guys plan to steal his recipes. To do so, they plan to send a single agent to parachute in a uniformlychosen random point in the region [10^{7},10^{7}] × [10^{7},10^{7}]. (This point need not be a lattice point.) Once the agent parachutes down that point, he then deploys in his exact location a special weapon called the pulverizer, which is designed to destroy walls. The pulverizer works by firing a laser that rotates 360 degrees clockwise, initially pointing north. This laser beam completely destroys the part of the wall it hits.
Once the walls are destroyed, the rest of the bad guys can now attack the house more easily.
Unfortunately, it's not guaranteed that the pulverizer will be able to destroy every bit of the wall. This is because the laser can only hit (and destroy) the first wall it hits, so if there's another part of the wall behind it, that part cannot be destroyed.
We will call the plan successful if all parts of the wall are destroyed. The following image illustrates it more clearly:
In this example, only the first image demonstrates a successful plan.
As head of security of Chef's house, can you determine the probability of a successful plan?
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N. The next N lines describe the wall. More precisely, the i^{th} line contains two integers x_{i} and y_{i} denoting that (x_{i}, y_{i}) is the i^{th} vertex of the polygon. The points are given in clockwise order around the boundary.
Output
For each test case, output a single real number denoting the probability of a successful plan by the bad guys. Your answer is considered correct if it is within an absolute error of 10^{6}.
Constraints
 x_{i}, y_{i} ≤ 10^{7}
 The points are given in clockwise order.
 The polygon is simple and has positive area, though some angles may be 180 degrees.
Subtasks
Subtask #1: (30 points)
Subtask #2: (70 points)
Example
Input: 2 5 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 0 0 6 700000 400000 300000 0 700000 400000 700000 400000 300000 0 700000 400000 Output: 0.25 0.00045
Explanation
The second example is depicted by the image above.
Author:  kevinsogo 
Tester:  mugurelionut 
Editorial  http://discuss.codechef.com/problems/ALLPOLY 
Tags  hard, july16, kernelpolygon, kevinsogo 
Date Added:  22062016 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 