레이팅 미적용농부 존(Farmer John)은 농장에 각각 크기가 정확히 K x K (1 <= K <= 1,000,000)인 정사각형 울타리 목초지 N개 (2 <= N <= 50,000)를 지을 계획이다. 목초지 i의 중심은 -1,000,000...1,000,000 범위의 정수 좌표를 가지는 점 (x_i, y_i)이다. 그런데 계획을 서둘러 마무리하다가, FJ는 실수로 두 목초지를 겹치는 위치에 배치했을지도 모른다는 것을 깨달았다 (겹친다는 것은 두 목초지가 양의 넓이를 공유한다는 뜻이다). 어떤 두 목초지도 정확히 같은 중심점을 가지지 않는다.
계획된 각 정사각형 목초지의 위치가 주어질 때, 겹치는 두 목초지가 공유하는 넓이를 계산하는 것을 FJ에게 도와주자. 어떤 두 정사각형도 겹치지 않으면 0을, 겹침이 두 개 이상의 목초지 쌍에서 발생하면 -1을 출력한다.
첫째 줄: 공백으로 구분된 두 정수 N과 K. K는 짝수임이 보장된다.
둘째 줄부터 1+N번째 줄까지: i+1번째 줄에 i번째 목초지의 중심을 나타내는 정수 x_i와 y_i가 주어진다.
겹치는 두 정사각형이 공유하는 넓이. 어떤 두 정사각형도 겹치지 않으면 0을, 겹침이 두 개 이상의 목초지 쌍에서 발생하면 -1을 출력한다.
squares.in · 출력을 쓸 파일 squares.out4 6
0 0
8 4
-2 1
0 720Output details: Pastures #1 and #3 overlap in 20 units of area.
riseoj 작성
출처 올림피아드 > USACO > 2012-2013 > January > Silver