Informatica Online Judge

  핵인싸 아무무 [2258 / 08D2]

Time Limit(Test case) : 1100(ms)
Number of users who solved : 14   Total Tried : 16


The Champion of this Problem (C++) : gs15120 - 0ms / 1926byte
My Best Submission (C++) : N/A

[34th 이윤상]
Writer ID : [gs16079]

Background

아무무는 협곡의 왕따이다.
그런데 어느날 웬걸, 하늘에서 협곡의 남작을 노리는 적들이 협곡에 떨어졌다.
하지만 애석하게도 적들은 낙하 충격으로 인해 다리가 부러져 협곡의 각 격자점에 앉아있다.
아무무는 자기라도 나서서 협곡을 지키겠다고 결심하였다.



아무무는 Q스킬, 끈적끈적한 붕대를 던져 적의 위치로 이동해 퇴치한다.
또, 아무무는 궁극기, 슬픈 미라의 저주를 내뿜어 일정 반경 안에 있는 적들을 퇴치한다.

적이 퇴치되면 그 자리에는 아무것도 없어 붕대를 던질 수 없고 궁극기는 한 번만 쓸 수 있기에 유의해야 한다.

처음 아무무의 붕대 길이 q와 궁극기 반경 r은 1이다. 아무무는 수련을 통해 q와 r의 길이를 하루에 1씩 늘릴 수 있다.

아무무는 한시라도 빨리 본인의 공적을 자랑하고 싶기에 최소의 날짜만 기다려 적을 싹 없애버리고 싶다.

하지만 아무무는 멍청해서 하염없이 기다리기만 할게 분명하다.
아무무를 도와 적을 모두 퇴치하기 위해서 기다려야 하는 최소 날 수를 알아보자.
(단, 모든 거리는 Euclidean distance로 정의된다.)

Input

첫 번째 줄에 적의 명수 N(1 <= N <= 9)이 주어진다.
다음 N줄에 걸쳐 적의 좌표 (x, y)가 주어진다. (1 <= x, y <= 100,000,000)
아무무는 (1, 1)에 있으며 모든 개체의 위치는 다르다.

Output

아무무가 기다려야 하는 최소 날 수를 출력한다.

IO Example

입력
5
3 1
5 2
7 3
8 2
5 5

출력
2

설명
2일을 기다린다면 길이는 3이다. (3,1)->(5,2)로 이동하고 궁극기를 통해 나머지를 퇴치할 수 있다.

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