Informatica Online Judge

  광역시 [0986 / 03DA]

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


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

[Codeforces.com]

Background

대한민국에서 도시의 인구가 $100$만명이 넘으면 광역시가 될 수 있는 필요조건이 된다.

좌표평면상에 있는 경곽시는 현재 $P$명의 인구를 가지고 있다.

그리고 각 좌표 $(x_i, y_i)$에 있는 도시들에 pi명씩 거주하고 있다.

경곽시에서 반지름 $r$만큼 원형으로 도시를 확장하려 한다. 경곽시의 확장 영역에 포함되면 이 도시의 인구는 경곽시로 편입된다. 이 때 경계 상에 위치하는 도시들도 포함되는 것으로 간주한다.

경곽시가 광역시가 되기 위해서 $100$만명 이상의 인구가 필요하다.

각 정보가 주어질 때, 경곽시가 $100$만 도시가 되기위해 필요한 최소 확장 반지름 $r$의 길이를 구하시오.

단 경곽시의 위치는 $0, 0$ 이다.

Input

첫 번째 줄에 도시의 수 $N$과 경곽시의 인구 $P$가 공백으로 구분되어 입력된다.

다음 줄부터 $N$줄에 걸쳐서 각 도시의 $x_i$, $y_i$, $p_i$가 공백으로 구분되어 입력된다.

[입력값의 정의역]

$1 \leq N \leq 10,000$
$0 \leq P \leq 999,999$
$-10,000 \leq x_i, y_i \leq 10,000$
$0 \leq p_i \leq 999,999$

[Sub task info]
#1 : $n \leq 20$
#2 : $n \leq 30$
#3, 4 : $n \leq 10,000$

Output

$100$만 도시가 되기 위해 필요한 확장거리 $r$의 최솟값을 소수점 $4$째자리에서 반올림하여 $3$째자리까지 출력한다. (%lf이용)
만약 $100$만 도시가 되기 불가능하면 $-1$을 출력한다.

IO Example

입력
4 999998
1 1 2
2 2 1
3 3 1
2 -2 1

출력
1.414

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