Informatica Online Judge

  화살표 그리기 [2326 / 0916]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 19   Total Tried : 20


The Champion of this Problem (C++) : gs19043 - ms / 709byte
My Best Submission (C++) : N/A

[KOI 2018]

Background

직선위에 N개의 점들이 주어지고 각 점은 N개의 색깔 중 하나를 가진다.

편의상, 색깔은 1부터 N까지의 수로 표시하고, 점들의 좌표는 모두 다르다.

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

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

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

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

Input

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

- 부분문제의 제약 조건

모든 부분문제에서 점들의 좌표 x와 색깔 y는 각각 $0≤x≤10^9$, $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$를 만족한다.

Output

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

IO Example

입력
4
0 1
1 2
3 1
4 1

출력
5

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]