Brother Rabbit fell into the habit of stealing dates from Brother Bear's
garden. He was stealing and stealing, and nothing could be done about that.
In order to save his dates, Brother Bear put n poles around the garden.
Then he walked around the garden several times with barbed wire making a fence.
But the next day there were Brother Rabbit's footprints in the garden again
and date stones were strewn everywhere. Then Brother Bear asked for Brother
Wolf's advice. Brother Wolf recommended to stretch ropes with bells
across the garden. He said: “Brother Rabbit will come for dates,
touch a rope, and you will hear the noise at once.”
Brother Bear took the advice and they started stretching ropes between the
poles. Brother Wolf would stand near a pole and tie a rope end to it, and Brother
Bear would count off k − 1 poles counter-clockwise
and tie the other end of the rope to the k-th pole. After that Brother
Wolf would come to another pole and so on, till ropes were stretched from
every pole. Satisfied, they went away to their homes.
That night Brother Bear slept light but didn't hear anything. In the morning he
went out into the garden and what did he saw? Brother Rabbit wasn't such a
fool. He noticed the ropes and didn't jump them over. He stole dates only from those
trees to which he could come without jumping over the ropes. Brother Bear
became upset at first, but then he rejoiced that a half of the garden had been
saved. Or less than a half? He couldn't calculate. Help Brother Bear.
Input
The first line contains the numbers n and k (3 ≤ n ≤ 300;
1 ≤ k < n). In the following n lines
you are given the coordinates of all the poles in the counter-clockwise order.
They are integers with absolute values not exceeding 10000. The garden is
convex; i.e., every straight segment connecting two points on different sides of
the fence lies inside the garden and may touch the fence at these two points
only.
Output
Output the ratio of the area saved by the ropes to the whole area inside the
fence accurate to 10−4.
Samples
input | output |
---|
5 3
0 0
20 0
20 20
10 30
0 20
| 0.466666667
|
6 2
0 2
-2 1
-2 -1
0 -2
2 -1
2 1
| 0.666666667
|
Problem Author: Pavel Egorov
Problem Source: USU Open Personal Contest 2009 (February 28, 2009)