Wall#6848

Wall

1 δευτερόλεπτο

64 megabyte

Πολύ δύσκολο

Once upon a time, a demanding King ordered his chief Architect to build a wall around the King's castle. The King was so insistent on efficiency that he ignored the Architect's proposals for a beautiful brick wall with a perfect shape and nice tall towers. Instead, he requested that the wall be built around the entire castle using as little stone and labor as possible, while still ensuring the wall does not approach the castle closer than a specified distance. The King also required that the Architect present, without delay, a plan for the wall that included the exact amount of resources needed for its construction.

Figure 1: Wall around the castle

Your task is to assist the Architect in creating a program that determines the minimum possible length of the wall that could be built around the castle to satisfy the King's requirements.

The task is somewhat simplified by the fact that the King's castle has a polygonal shape and is situated on flat ground. The Architect has already established a Cartesian coordinate system and has precisely measured the coordinates of all the castle's vertices in feet.

Είσοδος

The input file consists of multiple data sets.

The first line of each data set contains two integer numbers $N$ and $L$ separated by a space. $N$ ( $3$ ≤ $N$ ≤ $1000$ ) is the number of vertices in the King's castle, and $L$ ( $1$ ≤ $L$ ≤ $1000$ ) is the minimum number of feet that the King allows for the wall to approach the castle.

The next $N$ lines describe the coordinates of the castle's vertices in a clockwise order. The $i$ -th line contains two integer numbers $X_{i}$ X_i and $Y_{i}$ Y_i separated by a space ( $- 10000$ ≤ $X_{i}$ X_i, $Y_{i}$ Y_i ≤ $10000$ ), representing the coordinates of the i-th vertex. All vertices are distinct, and the sides of the castle do not intersect anywhere except at the vertices.

The end of the input file is indicated by $N = L = 0$ N = L = 0.

Έξοδος

For each case, write a line that contains the single number representing the minimal possible length of the wall in feet that could be built around the castle to satisfy the King's requirements. You must present the integer number of feet to the King, because floating-point numbers are not yet invented. However, you must round the result in such a way that it is accurate to $8$ inches ( $1$ foot is equal to $12$ inches), since the King will not accept a larger error in the estimates.

Παραδείγματα

Παράδειγμα 1