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

USU Open Personal Contest 2009

About     Problems     Submit solution     Judge status     Standings
Contest is over

B. Brother Bear's Garden

Time limit: 0.5 second
Memory limit: 64 MB
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

inputoutput
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)
To submit the solution for this problem go to the Problem set: 1681. Brother Bear's Garden