화살표 그리기

직선위에 \(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\)가 주어진다.

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

생성자가 기록되지 않았습니다.

출처 올림피아드 > 한국정보올림피아드 > KOI 2018 > 2차 대회 > 고등부 1번