시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 13 | 2 | 2 | 50.000% |
Vera has N rectangles. The i-th rectangle has corners (ai , bi) and (ci , di). 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 = \sum_{s=L}^{R}{f(s)}\). It can be seen that S = V√2 for some integer V. Compute the value of V.
Line 1 contains integers N, L, R (1 ≤ N ≤ 103, −2 × 108 ≤ L < R ≤ 2 × 108).
N lines follow. The i-th line contains integers ai, bi, ci, di (−108 ≤ ai < ci ≤ 108, −108 ≤ bi < di ≤ 108).
Print one line with one integer, the value of V.
3 -1 3 -2 -1 0 2 -1 0 1 1 1 -2 2 -1
7
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√2 ≈ 9.899.