JOI '18 Spring Camp Day 1 P2 - Fences

View as PDF

Submit solution

Points: 30 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem types

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 -10^{100} and 10^{100}, 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.

Input Specification

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 \le i \le N) of the following N lines contains four space separated integers A_i, B_i, C_i and D_i and (A_i, B_i) \neq (C_i, D_i). This means the i-th fence already built is the line segment connecting two points (A_i, B_i) and (C_i, D_i).

It's guaranteed that:

  • 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.

Output Specification

Output 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.

Constraints

  • 1 \le N \le 100
  • 1 \le S \le 200
  • -200 \le A_i \le 200 (1 \le i \le N)
  • -200 \le B_i \le 200 (1 \le i \le N)
  • -200 \le C_i \le 200 (1 \le i \le N)
  • -200 \le D_i \le 200 (1 \le i \le N)
  • (A_i, B_i) \neq (C_i, D_i) (1 \le i \le 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.
Subtask Points Additional constraints
1 18 N = 1
2 33 N \le 6
3 49 N \le 100

Sample Input 1

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

Sample Output 1

29.0000000000

Explanation for Sample 1

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.

Sample Input 2

1 2
-3 -3 -3 -2

Sample Output 2

16.0000000000

Explanation for Sample 2

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

Sample Input 3

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

Sample Output 3

14.1392801789

Sample Input 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

Sample Output 4

238.4778364511

Comments

There are no comments at the moment.