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

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

뱀파이어

시간 제한3초메모리 제한256 MB

요약
반지름이 r인 원 모양 태양이 수평선 아래에서 올라올 때 건물들에 완전히 가려지는 마지막 시각을 구합니다.
난이도

보통10점 중 6점

유형
기하, 구간, 정렬
정답자
아직 제출이 없습니다

문제

해가 지평선에서 떠오를 때 태양은 반지름 rr인 원이며, t=0t=0에 중심이 (0,−r)(0,-r)에 있고 초당 (0,1)(0,1)만큼 위로 이동한다. 각 건물은 지평선 위의 직사각형 실루엣으로 주어진다. 태양 전체가 실루엣들과 y≤0y \leq 0 영역의 합집합에 포함되는 마지막 시각을 구하라.

입력

여러 데이터셋이 주어진다. 각 데이터셋은 반지름 rr과 건물 수 nn으로 시작하고, 이어서 각 건물의 xli,xri,hix_{li}, x_{ri}, h_i가 한 줄씩 주어진다. r=n=0r=n=0이면 입력이 끝난다.

출력

각 데이터셋마다 햇빛이 가려지는 마지막 시각 tt를 오차 0.0010.001 이내로 소수 넷째 자리까지 출력한다.

예제1

  1. 예제 1

    입력
    2 3
-2 -1 3
0 1 3
2 3 3
2 2
-2 0 4
0 2 3
2 6
-3 3 1
-2 3 2
-1 3 3
0 3 4
1 3 5
2 3 6
2 6
-3 3 1
-3 2 2
-3 1 3
-3 0 4
-3 -1 5
-3 -2 6
0 0
    예상 출력
    0.0000
3.0000
2.2681
2.2679