시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 5960 | 1912 | 1492 | 33.687% |
직선위에 $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 ≤ $N$ ≤ 10를 만족한다.
점들의 색깔은 정확히 두 가지이고 점들의 개수는 1 ≤ $N$ ≤ 2,000를 만족한다.
점들의 개수는 1 ≤ $N$ ≤ 10,000를 만족한다.
점들의 개수는 1 ≤ $N$ ≤ 100,000를 만족한다.
4 0 1 1 2 3 1 4 1
5
4 1 1 0 2 4 3 3 4
0
9 10 2 11 3 20 2 22 1 25 1 0 1 4 2 5 2 7 2
45