Informatica Online Judge

  카카오 택시 [1681 / 0691]

Time Limit(Test case) : 2000 (ms)
Number of users who solved : 8   Total Tried : 10


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

[koistudy.net (32nd 최창호)]

Background

돈이 많은 koosaga는 가까운곳을 이동할 때도 택시를 애용한다.

그는 택시를 잡아주는 어플리케이션인 카카오 택시가 택시를 느리게 잡는 것에 매우 불만을 가지고 카카오를 인수해 알고리즘을 바꿔버릴려고 한다.

카카오 택시는 조금 특별한 방법으로 택시와 승객을 매치해준다.

먼저 다음과 같은 상황을 가정한다. 승객 $n$명과 택시 $n$개의 서로 다른 좌표가 주어진다.

그리고 각 승객마다 지불할 요금이 주어진다. 한 택시에 대해 거리와 요금이 모두 같은 두 승객은 존재하지 않는다.

모든 택시 기사들은 이 모든 정보들을 알고있고 다른 택시 기사들이 이 정보를 알고있다는 것도 알고 있다.

택시가 다른 좌표로 이동하는데 걸리는 시간이 자신의 좌표와의 택시거리에 비례한다. (택시의 속력은 모두 동일하다.)

택시가 한 번 승객을 태우면 목적지까지 데려다 주기위해 시간이 걸리기 때문에 다음 손님을 받을 수 없다.

모든 택시 기사들은 자신이 얻는 돈을 최대화하고 싶어하고 같은 돈을 번다면 이동거리를 최소화하고 싶어한다.

이러한 상황이 주어졌을 때 카카오 택시는 각 택시가 찾아갈 승객을 완벽하게 예측하여 승객과 택시를 매치 시켜준다.

자. 빠른 매치 알고리즘을 만들어 카카오를 인수한 koosaga를 도와주자!

Input

첫 줄에 승객과 택시의 수인 $n$이 주어진다. $(1 \leq n \leq 1,000)$

둘 째줄부터 $n+1$번째 줄까지 한 줄씩 택시의 좌표인 두 수가 주어진다.

$n+2$번째 줄부터 $2n+1$번째 줄까지 한 줄씩 승객들의 좌표와 요금이 주어진다.

좌표 : $0 \leq x, y \leq 10,000$
요금 : $1 \leq k \leq 10,000$

(모든 입력은 답이 유일하게 존재한다.)

Output

택시에 어떤 승객이 매치되는지 순서대로 출력해라.

IO Example

입력
2
0 0
5 5
1 1 4
2 2 5

출력
2 1

입력
5
0 0
1 0
2 0
3 0
4 0
6 0 3
7 0 9
8 0 4
9 0 1
10 0 2

출력
4 5 1 3 2

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