가장 큰 원
시간 제한5초메모리 제한128 MB
N개의 선분이 주어질 때, x축 위 [0,L] 구간에 중심을 둔 원이 어떤 선분과도 교차하지 않도록 하는 최대 반지름을 이분 탐색과 기하 거리 계산으로 구하는 문제입니다.
문제
이차원 평면에 개의 선분이 있다. 다음 조건을 모두 만족하는, 가장 큰 "비어 있는" 원의 반지름을 구하는 프로그램을 작성하시오.
- 원의 중심은 이다.
- (즉 중심은 축 위에 있다)
여기서 "비어 있는" 원이란 주어진 어떤 선분과도 교차하지 않는 원을 말한다. 단, 원이 선분에 접하는 것은 허용된다.
입력
첫째 줄에 테스트 케이스의 개수 가 주어진다. 각 테스트 케이스의 형식은 다음과 같다.
- 첫째 줄에 두 정수 과 이 주어진다 (, ).
- 이어지는 개의 줄에는 각 선분의 두 끝점을 나타내는 네 정수 가 순서대로 주어진다. 즉 그 선분의 양 끝점은 와 이다.
모든 좌표는 이상 이하의 정수이다.
출력
각 테스트 케이스마다 한 줄에, 가장 큰 원의 반지름을 소수점 아래 셋째 자리까지 반올림하여 출력한다.