Art Gallery
Time limit1sMemory limit128 MB
Compute the area of the kernel of a simple polygon, the region from which every boundary point is visible, using half-plane intersection.
- Level
Hard8 of 10
- Topics
- Geometry, Divide and conquer, Math
- Solved
- No attempts yet
Problem
The art galleries in the futuristic new building of the Center for Balkan Cooperation have the shape of polygons (not necessarily convex). During a large exhibition, keeping watch over all of the pictures is an important security concern.
For a given gallery, write a program that computes the area of the floor from which every point on the walls of the gallery is visible. A point on the floor can see a point on a wall when the straight segment joining them lies entirely inside the gallery, so you must find the area of the region from which the whole boundary can be seen at once.
Figure 1 shows the map of a gallery in a coordinate system; the region whose area you must report is shaded in Figure 2.
Input
The first line contains the number of tasks T. Each task begins with a line containing an integer N (5 ≤ N ≤ 1500), the number of vertices of the gallery's polygon. Each of the following N lines contains the coordinates of one vertex: two integers that fit in a 16-bit integer type (that is, in the range −32768 to 32767), separated by a single space. The vertices are listed in order around the boundary of the polygon. Immediately after the last vertex of one task, the next task follows in the same format.
Output
For each task, print on its own line the required area as a number with exactly two digits after the decimal point (rounded to the nearest hundredth).