## JOI Spring Camp '18 P2 - Fences

View as PDF

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

Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Mr. JOI owns a large lot in IOI Country. IOI Country is represented by a coordinate plane, with the -axis and the -axis being orthogonal. The point with the -coordinate and the -coordinate is denoted by . His lot is the area with the -coordinate and the -coordinate both between and , inclusive. There, he breeds cows in a pasture, which is the area with the -coordinate and the -coordinate both between and , 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 () costs . 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 and . This means the pasture is the area with the -coordinate and the -coordinate both between and , inclusive, and there have already been fences in Mr. JOI's lot.

The -th line () of the following lines contains four space separated integers , , and and . This means the -th fence already built is the line segment connecting two points and .

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 .

#### Constraints

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

#### 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 , and this is the minimum possible cost. In this sample input, other than , outputs such as and 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