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 Team.GOV contest. Petrozavodsk training camp. Summer 2011

About     Problems     Submit solution     Judge status     Standings
Contest is over

C. Laser Technologies

Time limit: 0.5 second
Memory limit: 64 MB
Almost every gift shop sells cubes and balls of glass with beautiful images inside them. Young girl Anya wanted to learn the way these images are created, so she entered the department of laser technologies. Now she knows that if two laser beams of frequency 3.1415 PHz intersect inside the glass object, the glass will become opaque at the intersection point, although this opacity will not block other laser beams passing through this point.
Now Anya herself wants to draw an image inside a polygonal prism. She decided to start with a flat image located in a section parallel to the base of the prism. Unfortunately, Anya spilled her tea on the second laser emitter, and it broke down. However, Anya knows that if two laser beams will pass through some point consecutively within a short period of time, this point will also become opaque. Now she wants to move the laser emitter all the way along the perimeter of the section. Laser beam will always lie inside the plane of this section. Laser beam should always be directed to a special receiver.
The frequency of the laser beams is extremely high, so the opaque points will be very close to each other, and will be recognized as parts of continuous curves. Anya wants to know the total length of all these curves, and asks for your help.
More formally, the section of the prism is a convex polygon with n vertices. Initially, Anya places an emitter at some point of its perimeter. She then places the receiver at some other point of the perimeter such that the distance between the emitter and the receiver measured along the perimeter is d. After that, Anya starts to move both the emitter and the receiver with equal constant speed in one direction along the perimeter. She stops when the emitter and the receiver move to their initial positions.
Problem illustration
The formal definition of the resulting opaque parts of curves is as follows. Consider some moment t when the emitter is at point A and receiver is at point B. In a near moment t + ε, the emitter (moving along the perimeter) arrives at some point A' while the receiver (moving with the same speed along some other part of the perimeter) arrives at some point B'. In general case, there will be exactly one intersection point of segments AB and A'B'. Now let ε → 0 to get the point which becomes opaque at the moment t. Do that for all possible moments t to get all the points which become opaque. This set of points in fact can be viewed as a set of curves. Your task is to find their total length.
On the illustration, the perimeter is a square, dashed lines represent the laser beam at different moments of time, and bold points are the points which become opaque as the emitter and the receiver move along the perimeter. The distance between the emitter and the receiver (measured along the perimeter) remains equal to the constant d. Note that it does not mean the lengths of dashed lines are equal. As you can see, the opaque points lie on a certain curve.


The first line contains an integer n (3 ≤ n ≤ 10 000). Each of the following n lines contains two integers which are the coordinates of vertices of the polygon in counter-clockwise order. The coordinates don't exceed 106 by their absolute values. It is guaranteed that no three vertices lie on the same line.
The last line contains a positive integer d. It is guaranteed that d doesn't exceed half of the length of polygon's perimeter and is strictly greater than the longest of its sides.


Output the total length of all curves formed by the opaque points with absolute or relative error not exceeding 10−6.


-1 0
1 0
0 10
0 0
10 0
10 10
0 10
Problem Author: Denis Dublennykh
Problem Source: Ural SU Team.GOV Contest. Petrozavodsk Summer Session, August 2011
To submit the solution for this problem go to the Problem set: 1853. Laser Technologies