아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

풍선을 터뜨리지 마세요

시간 제한7초메모리 제한128 MB

요약
바닥에 닿은 채 벽과 바늘에 닿지 않고 상자 안에 들어가는 가장 큰 구의 반지름을 구합니다.
난이도

보통10점 중 7점

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

문제

위가 열려 있고 밑면이 정사각형인 상자가 바닥에 놓여 있다. 상자 안을 들여다보면 밑면에 바늘 몇 개가 수직으로 꽂혀 있다.

이 상자에 공 모양 풍선을 넣으려고 한다. 풍선은 상자 밑면에 닿아야 하고, 네 옆면과 바늘 어디에도 파고들 수 없다. 겉면이 스치듯 맞닿는 것은 괜찮다. 이런 풍선 중 가장 큰 것의 반지름을 구하라.

옆면은 높이가 ww이고 두께가 없다. 그래서 반지름이 ww보다 큰 풍선은 옆면 위로 넘어가 부풀 수 있고, 이때는 옆면의 위쪽 모서리가 풍선을 막는다.

그림의 위쪽은 바늘이 꽂힌 배치이고, 아래쪽은 그 배치에 놓을 수 있는 가장 큰 풍선이다. 예제 입력의 첫 번째 데이터에 해당한다.

입력

입력은 데이터 여러 개로 이루어진다. 각 데이터의 형식은 다음과 같다.

n w
x1 y1 h1
.
.
.
xn yn hn

첫 줄에 양의 정수 nn과 ww가 공백 하나로 구분되어 주어진다. nn은 바늘의 개수이고 ww는 옆면의 높이다.

상자 밑면은 한 변의 길이가 100인 정사각형이고, 네 꼭짓점은 (0,0,0)(0, 0, 0), (0,100,0)(0, 100, 0), (100,100,0)(100, 100, 0), (100,0,0)(100, 0, 0)이다.

이어지는 nn개의 줄에 정수 xix_i, yiy_i, hih_i가 주어진다. ii번째 바늘은 (xi,yi,0)(x_i, y_i, 0)에 꽂혀 있고, 높이는 hih_i이다. 같은 자리에 꽂힌 바늘은 없다.

1≤n≤101 \le n \le 10, 10≤w≤20010 \le w \le 200, 0<xi<1000 < x_i < 100, 0<yi<1000 < y_i < 100, 1≤hi≤2001 \le h_i \le 200이다. 바늘과 옆면의 두께는 무시한다.

입력의 마지막 줄에는 0 두 개가 주어진다. 데이터의 개수는 1000개를 넘지 않는다.

출력

각 데이터마다 가장 큰 풍선의 반지름을 한 줄에 출력한다.

채점은 출력을 글자 그대로 비교한다. 반지름은 소수점 아래 여섯째 자리에서 반올림해서 다섯째 자리까지 출력한다. 반지름이 26이면 26.00000으로 출력한다. 모든 데이터의 정답은 반올림 경계에서 10−610^{-6}보다 멀리 떨어져 있으므로, 반지름을 오차 10−710^{-7} 안으로 구하면 출력이 하나로 정해진다.

예제1

  1. 예제 1

    입력
    5 16
    70 66 40
    38 52 20
    40 35 10
    70 30 10
    20 60 10
    1 100
    54 75 200
    1 10
    90 10 1
    1 11
    54 75 200
    3 10
    53 60 1
    61 38 1
    45 48 1
    4 10
    20 20 10
    20 80 10
    80 20 10
    80 80 10
    0 0
    
    예상 출력
    26.00000
    39.00000
    130.00000
    49.49777
    85.00000
    95.00000