만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

멀리 이사하기

시간 제한2초메모리 제한512 MB

요약
n개의 원판의 교집합 안에서 원점에서 가장 먼 점까지의 거리를 구해 소수 셋째 자리까지 반올림해 출력한다.
난이도

보통10점 중 6점

유형
기하, 이분 탐색
정답자
아직 제출이 없습니다

문제

토미는 대학을 막 졸업하고 첫 직장을 구하고 있다. 친구들과 가까이 사는 것을 중요하게 여기지만, 부모님과는 최대한 멀리 떨어져 살고 싶다.

토미의 친구 nn명이 사는 위치와, 각 친구에게서 떨어져 살아도 괜찮은 최대 거리가 주어진다. 부모님은 좌표평면의 원점 (0,0)(0, 0)에 산다.

토미가 살 집의 좌표 (px,py)(p_x, p_y)는 모든 친구 ii에 대해 (px−xi)2+(py−yi)2≤di\sqrt{(p_x - x_i)^2 + (p_y - y_i)^2} \le d_i를 만족해야 한다. 이 조건을 만족하는 점 중에서 원점까지의 거리가 가장 먼 점을 찾아, 그 거리를 구하라. 조건을 만족하는 점은 항상 하나 이상 있다.

입력

입력은 테스트 케이스 하나로 이루어진다.

첫 줄에 토미의 친구 수 nn (1≤n≤501 \le n \le 50)이 주어진다. 다음 nn개의 줄에는 각각 정수 xx, yy (−1000≤x,y≤1000-1000 \le x, y \le 1000)와 dd (1≤d≤10001 \le d \le 1000)가 공백으로 구분되어 주어진다. (x,y)(x, y)는 친구가 사는 좌표이고, dd는 토미가 그 친구에게서 떨어져 살 수 있는 최대 거리다.

출력

모든 친구의 조건을 지키면서 토미가 부모님에게서 떨어질 수 있는 최대 거리를 한 줄에 출력한다. 반올림해서 소수점 아래 정확히 셋째 자리까지 출력한다.

예제2

  1. 예제 1

    입력
    4
    1 0 1
    0 1 1
    -1 0 1
    0 -1 1
    
    예상 출력
    0.000
    
  2. 예제 2

    입력
    2
    -1 0 1000
    2 0 1000
    
    예상 출력
    999.999