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 uniformly-chosen random point in the region [-107,107] × [-107,107]. (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?
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 ith line contains two integers xi and yi denoting that (xi, yi) is the ith vertex of the polygon. The points are given in clockwise order around the boundary.
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.
- |xi|, |yi| ≤ 107
- The points are given in clockwise order.
- The polygon is simple and has positive area, though some angles may be 180 degrees.
Subtask #1: (30 points)
Subtask #2: (70 points)
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
The second example is depicted by the image above.
|Tags||hard, july16, kernel-polygon, kevinsogo|
|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|
Fetching successful submissions
If you are still having problems, see a sample solution here.