Submit solution

Points: 15 (partial)
Time limit: 2.0s
Memory limit: 512M

Problem type
2017 Fall Waterloo Local ACM Contest, Problem E

Vera has N rectangles. The i-th rectangle has corners (a_i, b_i) and (c_i, d_i). Let U be the union of the N rectangles. The intersection of U and the line y = s - x is composed of disjoint line segments (maybe degenerate ones). Let f(s) be the sum of the lengths of these line segments or be zero if the intersection is empty.

Given integers L and R, let S = \Sigma_{s=L}^{R} f(s). It can be seen that S = V \sqrt{2} for some integer V. Compute the value of V.


Line 1 contains integers N, L, R (1 \le N \le 10^3, -2 \times 10^8 \le L < R \le 2 \times 10^8).

N lines follow. The i-th line contains integers a_i, b_i, c_i, d_i (-10^8 \le a_i < c_i \le 10^8, -10^8 \le b_i < d_i \le 10^8).


Print one line with one integer, the value of V.

Sample Input

3 -1 3
-2 -1 0 2
-1 0 1 1
1 -2 2 -1

Sample Output



The below figure illustrates the first example when s = 0. f(0) is the sum of the lengths of the two thick blue line segments. Note that S = 7 \sqrt{2} \approx 9.899.


There are no comments at the moment.