무한 길이 물풍선

NYPC 2024 · Round 1

배찌는 무한한 길이의 폭발 범위를 가지는 물풍선 스킬을 터득하였다. 이 스킬을 사용하기 위해 배찌는 우선 2차원 평면의 NN 개의 좌표에 물풍선을 놓는다.

스킬을 사용하면 동일한 xx 좌표를 가진 두 점에 물풍선이 있는 경우 해당 xx 좌표의 모든 점이 물풍선의 폭발 범위에 들어간다. 즉, 수직인 직선 전부가 물풍선의 폭발 범위가 된다.

또, 동일한 yy 좌표를 가진 두 점에 물풍선이 있는 경우 해당 yy 좌표의 모든 점이 물풍선의 폭발 범위에 들어간다. 즉, 수평인 직선 전부가 물풍선의 폭발 범위가 된다.

배찌가 물풍선을 놓은 좌표들을 입력으로 받아 물풍선의 폭발 범위가 되는 수직, 수평 직선의 개수를 계산하는 프로그램을 작성하라. 서로 다른 두 개 이상의 물풍선 쌍이 만드는 폭발 범위가 완전히 일치하는 경우, 즉 동일한 직선이 되는 경우는 하나로 세어야 한다.

입력 형식

첫 줄에 점의 개수를 나타내는 정수 NN이 주어진다. (1N1000001 \le N \le 100\,000)

이어지는 NN 개의 줄의 ii 번째 줄에는 ii 번째 물풍선이 놓인 좌표를 나타내는 두 정수 xix_iyiy_i가 공백으로 구분되어 주어진다. (1xi,yi10000000001 \le x_i, y_i \le 1\,000\,000\,000)

주어지는 물풍선의 좌표는 서로 다르다.

출력 형식

첫 줄에 물풍선의 폭발 범위가 되는 수직, 수평 직선의 개수를 출력한다.

예제

입력

4 1 1 2 2 3 1 2 1

출력

2

예제 설명

물풍선이 놓인 점 (2,2)(2, 2)(2,1)(2, 1)을 보면 xx 좌표가 같으므로 수직인 직선 하나가 폭발 범위가 된다.
(1,1)(1, 1)(2,1)(2, 1)을 보면 yy 좌표가 같으므로 수평인 직선 하나가 폭발 범위가 된다.
(2,1)(2, 1)(3,1)(3, 1)을 보면 yy 좌표가 같으므로 수평인 직선 하나가 폭발 범위가 된다.
(1,1)(1, 1)(3,1)(3, 1)을 보면 yy 좌표가 같으므로 수평인 직선 하나가 폭발 범위가 된다.
그런데, 수평인 직선 33 개는 모두 완전히 일치하므로 11 개로 세어야 한다.

따라서 이 경우의 답은 22가 된다.

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.

종류 1: 13

N20;N \le 20; xi,yi20x_i, y_i \le 20

종류 2: 16

N1000N \le 1\,000; xi,yi100x_i, y_i \le 100

종류 3: 14

N1000N \le 1\,000

종류 4: 57

추가적인 제한 조건이 없음.

해설