Informatica Online Judge

  보스몬스터 학살하기 [0634 / 027A]

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


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[]

Background

Diablo II국에는 나라의 안전을 위협하는 n마리의 보스몬스터가 곳곳에 있다.

하지만 Diablo II국에는 강력하고 정의로운 마법사인 qwerty414가 있어서 나라의 안전을 지키기 위해 그의 집에서 출발하여 보스몬스터를 소탕하기로 결정했다.

강력한 qwerty414는 어떤 보스몬스터를 만나든 바로 없애버릴 수 있다. 하지만 qwerty414는 멋을 위해 항상 바닥에 불을 지르는 마법인 Blazing Step을 쓰고 다니는데, 이 불은 꺼지지도 않고 자신이 지나가도 상처를 받고 쓰러져버린다.

qwerty414는 모든 보스몬스터를 없앤 이후에는 자신의 집으로 돌아와야 한다.

또, 그는 강력하지만 멍청해서 한 보스몬스터를 정해 그 보스몬스터를 향해서 일직선으로만 움직이고, 보스몬스터를 없앤 이후에만 다른 보스몬스터나 집을 향해 방향을 바꿀 수 있다.

qwerty414는 모든 보스몬스터를 잡고 집으로 돌아오는 방법을 찾고 싶어 한다. qwerty414를 도와주는 프로그램을 만들자.

Input

1번째 줄에 보스몬스터의 수를 나타내는 가 입력된다.
2번째 줄에는 qwerty414의 집의 좌표를 나타내는 가 소수점 둘째자리까지 입력된다.

3번째 줄부터 번째 줄까지는 각각 보스몬스터 의 좌표를 나타내는 실수의 쌍 이 소수점 둘째자리까지 입력된다.

은 100000이하의 자연수이고, 는 절댓값이 10000이하인 실수이다.

어떤 세 몬스터나 집도 한 직선상에 있지는 않다.

Output

잡으러 가는 보스몬스터의 번호 개를 순서대로 출력한다.
보스몬스터를 잡으러 움직이는 경로에서 교차하는 부분이 있으면 안 된다.

[테스트케이스]
n<=20 : 30%
n<=3000 : 70%
추가 : n<=1000000일 때도 풀 수 있을까?

IO Example

입력
3
0.00 0.00
1.00 1.00
-1.00 1.00
0.00 2.00

출력
1 3 2

* 설명 : 1 2 3 의 경우에는 보스몬스터 1을 잡고 2를 잡으러 움직인 경로와 3을 잡고 집으로 돌아오는 경로가 교차해 qwerty414가 상처를 받고 쓰러지게 된다.

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