What will happen at night in a museum is always unpredictable, so is in an art gallery. As a night guard in the “Mike don’t know” art gallery, Mike is trying really hard to stand at a point which can see whole place inside the gallery. But it is too tired to stand alone at a single point in the gallery all night. Help Mike to calculate the total area he can walk back and forth, and still can see whole place inside the gallery through the night. The art gallery is guaranteed to be a simple convex polygon with n sides.
There are multiple test cases. For each test case, the first line contains an integer n (3 <= n <= 100,000). Next n lines contain the coordinates of each corner of the gallery, with either clockwise or counter-clockwise order. n = 0 terminates the input. All coordinates’ values are floating-point number with absolute value no more than 1000, and they are always an integral multiple of 1/100.
For each test case, output the total area up to 3 digits after the decimal point.
4 0 0 1 0 1 1 0 1 3 0 0 0 10.00 10.00 0 0
1.000 50.000
Migrated from old NTUJ.
Tmt
| No. | Testdata Range | Score |
|---|