문제
직선위에 N개의 점들이 주어지고 각 점은 N개의 색깔 중 하나를 가진다.
편의상, 색깔은 1부터 N까지의 수로 표시하고, 점들의 좌표는 모두 다르다.
각 점 p에 대해서, p에서 시작하는 직선 화살표를 이용해서 다른 점 q에 연결하려고 한다.
여기서, 점 q는 p와 같은 색깔의 점들 중 p와 거리가 가장 가까운 점이어야 한다.
만약 가장 가까운 점이 두 개 이상이면 아무거나 하나를 선택한다.
각 점 p에서 시작하여 위 조건을 만족하는 q로 가는 하나의 화살표
특별히 점 p에 대해서 수평선상 에 같은 색깔의 다른 점이 없다면
여기서
예를 들어, 점들을 순서쌍 (좌표, 색깔)로 표시할 때, p1 = (0, 1), p2 = (1, 2), p3 = (3, 1), p4= (4, 1)라고 하자.
점 p1의
점 p2의 경우는 같은 색깔의 다른 점이 존재하지 않는다.
따라서 모든 화살표들의 길이 합은
점들의 좌표와 색깔이 주어질 때, 모든 점에서 시작하는 화살표들의 길이 합,
다시 말해서,
입력
표준 입력으로 다음 정보가 주어진다.
첫 번째 줄에는 점들의 개수를 나타내는 정수 N이 주어진다.
다음 N개의 줄 각각에는 점의 좌표와 색깔을 나타내는 두 정수 x와 y가 주어진다.
출력
표준 출력으로 모든 점에서 시작하는 화살표들의 길이의 합을 출력한다.
[제약 조건]
모든 부분문제에서 점들의 좌표 x와 색깔 y는 각각
부분문제
번호 | 점수 | 조건 |
---|---|---|
#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
5
예제2
4
1 1
0 2
4 3
3 4
0
예제3
9
10 2
11 3
20 2
22 1
25 1
0 1
4 2
5 2
7 2
45