실행 시간 제한 | 메모리 제한 |
---|---|
1 초 | 128 MB |
축구장 관리자인 성훈은 그의 축구장에 N (2 <= N <= 50,000) 개의 정확히 K x K (1 <= K <= 1,000,000) 크기의 잔디밭을 조성할 계획을 하고 있다. 잔디밭 i는 -1,000,000...1,000,000 범위의 정수 좌표를 가진 지점 (x_i, y_i)의 중심에 위치해 있다.
그러나 계획이 잘못되어, 실수로 두 곳의 잔디밭의 위치가 겹치도록 배치되었을 수도 있다는 것을 성훈은 알게 된다.(두 잔디밭이 겹친다는 말은 두 잔디밭이 공통의 양의 영역을 공유한다는 뜻이다).
두 개의 잔디밭이 정확히 같은 중심점을 공유하는 것은 없다. \n 각 정사각형 잔디밭의 위치가 주어질 때, 성훈이 두 개의 겹치는 잔디밭에 의해 공유되는 영역을 계산하는 것을 도와주십시오. 두 개의 정사각형이 겹치지 않을 경우 0을 출력하고, 두 개 이상의 쌍에 대해 겹침이 발생하면 -1을 출력하십시오.
4 6 0 0 8 4 -2 1 0 7
20
출처: USACO 2013 January Contest, Silver Problem 2. Square Overlap