파일 업로드

잔디밭 공유 면적

profile
실행 시간 제한메모리 제한
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을 출력하십시오.

💻 입력
  • 첫 번째 줄 : 두 개의 공백으로 구분된 정수, N과 K. K는 짝수라는 것이 보장된다.
  • 두 번째 줄..1+N 번째 줄 : i+1 번째 줄에는 정수 x_i와 y_i가 포함되어 있으며, i 번째 잔디밭의 중심을 설명한다.
🖨️ 출력
  • 첫 번째 줄 : 두 개의 겹치는 정사각형에서 공유하는 영역. 두 개의 정사각형이 겹치지 않을 경우 0을 출력하고, 두 개 이상의 쌍에 대해 겹침이 발생하면 -1을 출력하십시오.

💻 예제 입력 1
4 6
0 0
8 4
-2 1
0 7
🖨️ 예제 출력 1
20

출처: USACO 2013 January Contest, Silver Problem 2. Square Overlap