강한 북서풍이 불고 있다. 이 뜻은 동쪽과 남쪽 사이의 모든 방향으로 항해할 수 있다는 뜻이다. 북쪽이나 서쪽으로 항해하는 것은 불가능하다.
작은 섬이 여러 개 있는 바다가 있다. 섬은 좌표 평면의 한 점으로 나타낼 수 있다. y 좌표가 증가하는 방향은 북쪽, x좌표가 증가하는 방향은 동쪽이다. 북서풍을 타고 항해할 수 있는 섬의 쌍의 수를 구하는 프로그램을 작성하시오.
’’’
Input
‘’’
첫째 줄에 테스트 케이스의 개수가 주어진다.
각 테스트 케이스의 첫째 줄에는 섬의 수 n (1 ≤ n ≤ 75000)이 주어진다. 다음 n개 줄에는 각 섬의 좌표 x_i, y_i가 주어진다. 두 섬의 좌표가 같은 경우는 없다. (-10^9 ≤ x_i, y_i ≤ 10^9)
’’’
Output
‘’’
각 테스트 케이스에 대해서, 북서풍을 타고 항해할 수 있는 섬의 쌍의 수를 출력한다.
가장 먼저 생각했던 것은 항해는 동쪽과 남쪽으로만 항해가 가능하므로, x의 크기는 증가, y의 크기는 감소해야 한다고 생각했다.
그런데 x,y의 좌표가 -10^9 ~ 10^9까지 가능하므로 x,y의 값을 전부 좌표로 표현한다음에 세그먼트 트리 기법이나 브루트 포스 기법은 메모리 초과 및 시간 초과가 분명했다.
그래서 입력받은 섬의 x, y 좌표 값을 x좌표를 기준으로 정렬한 다음에, y좌표를 좌표압축 기법을 사용해 상대적인 값으로 나타내고 이를 이용해서 세그먼트 트리 기법을 이용하기로 했다.