시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 1763 520 424 62.722%

문제

직선위에 $N$개의 점들이 주어지고 각 점은 $N$개의 색깔 중 하나를 가진다. 편의상, 색깔은 1부터 $N$까지의 수로 표시 하고, 점들의 좌표는 모두 다르다.

각 점 $p$에 대해서, $p$에서 시작하는 직선 화살표를 이용해서 다른 점 $q$에 연결하려고 한다. 여기서, 점 $q$는 $p$와 같은 색깔의 점들 중 $p$와 거리가 가장 가까운 점이어야 한다. 만약 가장 가까운 점이 두 개 이상이면 아무거나 하나를 선택한다.

각 점 $p$에서 시작하여 위 조건을 만족하는 $q$로 가는 하나의 화살표 $\vec{\ell_{p}}$를 그린다. 특별히 점 $p$에 대해서 수평선 상에 같은 색깔의 다른 점이 없다면 $\left|\vec{\ell_{p}}\right|=0$. 여기서 $\left|\vec{\ell_{p}}\right|$는 화살표 $\vec{\ell_{p}}$의 길이를 나타낸다.

예를 들어, 점들을 순서쌍 (좌표, 색깔) 로 표시할 때, $p_1$ = (0, 1), $p_2$ = (1, 2), $p_3$ = (3, 1), $p_4$ = (4, 1)라고 하자. 점 $p_1$의 화살표 $\left|\vec{\ell_{p_1}}\right|$은 $p_1\rightarrow p_3$ 로 연결된다. 점 $p_3$과 $p_4$의 화살표 $\left|\vec{\ell_{p_3}}\right|$과 $\left|\vec{\ell_{p_4}}\right|$는 각각 $p_3\rightarrow p_4$와 $p_4\rightarrow p_3$로 연결된다. 점 $p_2$의 경우는 같은 색깔의 다른 점이 존재하지 않는다. 따라서 모든 화살표들의 길이 합은 $\left|\vec{\ell_{p_1}}\right|+\left|\vec{\ell_{p_2}}\right|+\left|\vec{\ell_{p_3}}\right|+\left|\vec{\ell_{p_4}}\right|=3+0+1+1=5$이다.

점들의 좌표와 색깔이 주어질 때, 모든 점에서 시작하는 화살표들의 길이 합, 다시 말해서, $\displaystyle\sum_{p}\left|\vec{\ell_{p}}\right|$을 출력하는 프로그램을 작성하시오.

입력

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 점들의 개수를 나타내는 정수 $N$이 주어진다. 다음 $N$개의 줄 각각에는 점의 좌표와 색깔을 나타내는 두 정수 $x$와 $y$가 주어진다.

출력

표준 출력으로 모든 점에서 시작하는 화살표들의 길이 합을 출력한다.

제한

모든 서브태스크에서 점들의 좌표 $x$와 색깔 $y$는 각각 0 ≤ $x$ ≤ 109, 1 ≤ $y$ ≤ $N$를 만족한다.

서브태스크 1 (21점)

점들의 색깔은 모두 동일하고 점들의 개수는 1 ≤ $N$ ≤ 10를 만족한다.

서브태스크 2 (12점)

점들의 색깔은 정확히 두 가지이고 점들의 개수는 1 ≤ $N$ ≤ 2,000를 만족한다.

서브태스크 3 (29점)

점들의 개수는 1 ≤ $N$ ≤ 10,000를 만족한다.

서브태스크 4 (38점)

점들의 개수는 1 ≤ $N$ ≤ 100,000를 만족한다.

예제 입력 1

4
0 1
1 2
3 1
4 1

예제 출력 1

5

예제 입력 2

4
1 1
0 2
4 3
3 4

예제 출력 2

0

예제 입력 3

9
10 2
11 3
20 2
22 1
25 1
0 1
4 2
5 2
7 2

예제 출력 3

45

출처

Olympiad > 한국정보올림피아드 > KOI 2018 > 고등부 1번

  • 데이터를 추가한 사람: sait2000