문제

• 
• 시간 제한: 256MB
• 메모리 제한: 1초

Problem Analysis

Naive 하게 풀면, N(N-1) 가지 쌍을 모두 조사하면 되지만 오래 걸린다. 대신, Segment Tree로 원하는 범위에 존재하는 섬을 조사할 수 있다면, 시간을 단축시킬 수 있을 것이다.

Algorithm

남쪽 섬부터 시작해서 북쪽 섬 순서로, 같은 y에서는 동쪽에서 서쪽으로 다음과 같이 조사한다.
1. 현재 섬의 x값 이상에 존재하는 섬의 수를 ST로 구한다.
2. 현재 섬을 ST에 추가한다.

Data Structure

• ST[]: x 값을 기준으로 섬의 수를 저장
• points[]: y 오름차순, x 내림차순으로 섬을 저장

결과

Other

시간 복잡도는 O(NlogN)이다.

Segment Tree를 사용하기 위해, 좌표를 압축시켜 공간을 최소화한다.