Problem B
Big Brother
A good CCTV camera is expensive, so ideally you would only use one. It would obviously have to be placed somewhere where the entire office floor can be overlooked, so there are no walls blocking some dark corner of the floor where your workforce might hide.
While looking at the floor map, which can be modelled as a simple polygon, you are not sure if this is possible. Since the task is way above the paygrade of everyone else in the company you will have to write the program figuring this out yourself. If it is possible, you also want to know the area of the surface where the camera could be placed. See Figure 1 for an example.
Input
The first line of input contains an integer
Output
Output the area of the region of the map where a CCTV camera
could be placed so that the rest of the office can be observed.
(If it is not possible to put the camera anywhere, this area is
The answer must be correct with a relative of at most
Sample Input 1 | Sample Output 1 |
---|---|
8 0 0 0 1 1 1 1 2 2 2 2 1 3 1 3 0 |
1.0 |
Sample Input 2 | Sample Output 2 |
---|---|
8 0 0 0 2 1 2 1 1 2 1 2 2 3 2 3 0 |
0.0 |
Sample Input 3 | Sample Output 3 |
---|---|
6 140 62 97 141 68 156 129 145 153 176 130 109 |
48.80349500 |