Cut the Cake

Time Limit: 5000/5000 MS (Java/Others)

Memory Limit: 102400/102400 K (Java/Others)

Description

Mehmet is a nut cake seller. As the whole cake is too large and too heavy, a customer generally buys a specified part of it. The whole cake is a rectangle, while the specified part is a convex polygon region inside the rectangle. To get such specified part, Mehmet uses his sword to cut the cake. The only operation he can do is splitting a piece of cake into two parts by a straight cutting. As the cake is very solid, it cost as much as 1 unit energy to cut each length of cake. What's the minimum energy Mehmet has to consume to satisfy the customer?

Input

There are multiple test cases. Process to the End of File.

The first line of each test cases contains three integers 3≤N≤100, 0<W≤5000, 0<H≤5000, where W and H are the width and height of the nut cake. The next N lines are the vertices of the specified part in clockwise or counterclockwise order. Each line contains two integers 0<Xi<W and 0<Yi<H.

Output

For each test case, output the minimum energy with six digits after decimal point.

Sample Input

4 100 100 10 10 20 10 20 20 10 20 5 40 30 12 25 28 25 32 20 20 8 8 20

Sample Output

150.000000 109.494748

Hint

zhuyuanchen520

Source

2013 Multi-University Training Contest 9

提交代码