ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Ural SU contest. Petrozavodsk training camp. Winter 2006

About     Problems     Submit solution     Judge status     Standings
Contest is over

F. Light

Time limit: 3.0 second
Memory limit: 64 MB
Santa Claus Petrovich moved to a new hut. It consists of only one room. Its floor has the form of a simple polygon (not necessarily convex) with N vertices. It was dark in the hut at first, but then Petrovich hung a lamp at the point with projection (X0, Y0). Which area of the room is illuminated by the lamp?


The first line contains the coordinates of the lamp (X0, Y0). You may regard the lamp as a material point. The second line contains the integer 3 ≤ N ≤ 50000. In the next N lines there are coordinates (Xi, Yi) of vertices of the N-gon. The vertices are given in the counter-clockwise order. All the coordinates are given as pairs of real numbers separated with a space, 0 ≤ Xi,Yi ≤ 1000. The coordinates contain not more than four fractional digits. It is guaranteed that the lamp is strictly inside the room.


Output the area S of the illuminated part of the room. The area must be given with accuracy of at least two fractional digits.


1.0 1.0
0 0
3 0
3 2
2 2
2 3
0 3
Problem Author: Dmitry Ivankov (idea of Alexander Ipatov)
Problem Source: Ural SU Contest. Petrozavodsk Winter Session, January 2006
To submit the solution for this problem go to the Problem set: 1464. Light