시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 3 3 3 100.000%

문제

Mr. JOI owns a large lot in IOI Country. IOI Country is represented by a coordinate plane, with the X-axis and the Y-axis being orthogonal. The point with the X-coordinate x and the Y-coordinate y is denoted by (x, y). His lot is the area with the X-coordinate and the Y-coordinate both between −10100 and 10100, inclusive. There, he breeds cows in a pasture, which is the area with the X-coordinate and the Y-coordinate both between −S and S , inclusive.

Mr. JOI decided to enclose the pasture with some fences in order to keep the cows. A fence is represented by a line segment whose length is a positive real number. He will enclose the pasture in such a way that it is impossible to go from any point inside the pasture to the outside of his lot without passing any points where a fence exists (including the endpoints of the fences). There have already been some fences in the lot, which he may use to enclose the pasture. For any two fences among these, if they have a common point, it is an endpoint of at least one of the two.

Mr. JOI can build any number of new fences. A new fence can be of arbitrary length and of arbitrary direction, as long as it passes neither inside the pasture nor outside the lot. He may build a fence which passes along the boundary of the pasture. Building a new fence with length l (l > 0) costs l. It may be that two fences intersect, an endpoint of a fence coincides with an endpoint of another fence, or an endpoint of a fence lies on another fence.

Mr. JOI wants to enclose the pasture with as low cost as possible.

Given the size of the pasture and the data of fences already built, write a program which calculates the minimum total cost needed to enclose the pasture.

입력

Read the following data from the standard input.

  • The first line of the input contains two space separated integers N and S . This means the pasture is the area with the X-coordinate and the Y-coordinate both between −S and S , inclusive, and there have already been N fences in Mr. JOI’s lot.
  • The i-th line (1 ≤ i ≤ N) of the following N lines contains four space separated integers Ai, Bi, Ci and Di. This means the i-th fence already built is the line segment connecting two points (Ai, Bi) and (Ci, Di).

출력

Write one line to the standard output. The output should contain the minimum total cost needed to enclose the pasture. You may print any number of digits after the decimal point, but the absolute error between your output and the correct answer must be at most 0.01.

제한

  • 1 ≤ N ≤ 100.
  • 1 ≤ S ≤ 200.
  • −200 ≤ Ai ≤ 200 (1 ≤ i ≤ N).
  • −200 ≤ Bi ≤ 200 (1 ≤ i ≤ N).
  • −200 ≤ Ci ≤ 200 (1 ≤ i ≤ N).
  • −200 ≤ Di ≤ 200 (1 ≤ i ≤ N).
  • (Ai , Bi), (Ci , Di) (1 ≤ i ≤ N).
  • No fence in the input passes strictly inside the pasture.
  • For any two distinct fences in the input, if they have a common point, it is an endpoint of at least one of the two.

예제 입력 1

3 4
-3 5 1 8
-4 3 -4 6
5 1 7 2

예제 출력 1

29.0000000000

The fences already built in Sample Input 1 are depicted on the left of the following picture. The dotted square at the center is the boundary of the pasture.

A way to enclose the pasture in this sample input is depicted on the right, where thin line segments represent new fences. Building these fences costs 29, and this is the minimum possible cost. In this sample input, other than 29.0000000000, outputs such as 29 and 28.999 are also judged correct.

예제 입력 2

1 2
-3 -3 -3 -2

예제 출력 2

16.0000000000

Note that it is fine to use no fences already built at all.

예제 입력 3

4 3
4 -1 3 4
-4 2 -2 4
-4 0 -5 6
0 -6 5 -2

예제 출력 3

14.1392801789

예제 입력 4

10 80
175 95 60 -146
-106 57 18 185
190 -68 177 -142
84 -195 127 -179
34 143 126 69
-92 133 -190 80
-157 -66 -119 -161
-85 -124 129 -171
141 181 175 175
107 -38 150 148

예제 출력 4

238.4778364511