3234 : 화살표(고)
- 제한시간
- 1000 ms
- 메모리제한
- 128 MB
- 해결횟수
- 28 회
- 시도횟수
- 90 회
문제
직선위에 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의 화살표 은 p1→ p3로 연결된다.
점 p3 과 p4의 화살표 과
는 각각 p3→p4와 p4→p3로 연결된다.
점 p2의 경우는 같은 색깔의 다른 점이 존재하지 않는다.
따라서 모든 화살표들의 길이 합은 이다.
점들의 좌표와 색깔이 주어질 때, 모든 점에서 시작하는 화살표들의 길이 합 ,
다시 말해서, 을 출력하는 프로그램을 작성하시오.
소스파일의 이름은 arrow.c 또는 arrow.cpp를 권장하지만, 서버에 제출하는 데는 다른 이름도 상관없다.
입력형식
표준 입력으로 다음 정보가 주어진다.
첫 번째 줄에는 점들의 개수를 나타내는 정수 N이 주어진다.
다음 N개의 줄 각각에는 점의 좌표와 색깔을 나타내는 두 정수 x와 y가 주어진다.
출력형식
표준 출력으로 모든 점에서 시작하는 화살표들의 길이의 합을 출력한다.
[부분문제의 제약 조건]
모든 부분문제에서 점들의 좌표 x와 색깔 y는 각각 0 ≤ x ≤109, 1 ≤ y ≤ N를 만족한다.
* 부분문제 1: 전체 점수 100점 중 21점에 해당하며, 점들의 색깔은 모두 동일하고 점들의 개수는 1 ≤ N ≤ 10를 만족한다.
* 부분문제 2: 전체 점수 100점 중 12점에 해당하며, 점들의 색깔은 정확히 두 가지이고 점들의 개수는 1 ≤ N ≤ 2,000를 만족한다.
* 부분문제 3: 전체 점수 100점 중 29점에 해당하며, 점들의 개수는 1 ≤ N ≤ 10,000를 만족한다.
* 부분문제 4: 전체 점수 100점 중 38점에 해당하며, 점들의 개수는 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 |