Almost every gift shop sells cubes and balls of glass with beautiful images
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
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.
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.
Problem Author: Denis Dublennykh
Problem Source: Ural SU Team.GOV Contest. Petrozavodsk Summer Session, August 2011