Mock CCO '18 Contest 1 Problem 4 - A Rectangle Problem

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 0.18s
Memory limit: 16M

Problem type

Given a list of N rectangles, compute the minimum perimeter of a polygon with axis-aligned sides such that the first rectangle is contained within the polygon and no point on the perimeter of the polygon lies inside, but not on the perimeter, of any of the rectangles.

Constraints

1 \le N \le 100

For any rectangle, 0 \le x_{1_i} < x_{2_i} \le 10^4 and 0 \le y_{1_i} < y_{2_i} \le 10^4.

For at most 30% of marks, N \le 10.

Input Specification

The first line will contain a single integer, N.

The next N lines each contain four integers, x_{1_i}, y_{1_i}, x_{2_i}, and y_{2_i}, defining the vertices of one of the rectangles.

Note that the second line of input corresponds to the rectangle that must be contained within the polygon.

Output Specification

Output the desired perimeter of the polygon.

Sample Input

4
8 4 13 8
2 1 6 7
4 7 9 11
14 7 19 11

Sample Output

32

Comments

There are no comments at the moment.