가장 큰 원

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

요약
N개의 선분이 주어질 때, x축 위 [0,L] 구간에 중심을 둔 원이 어떤 선분과도 교차하지 않도록 하는 최대 반지름을 이분 탐색과 기하 거리 계산으로 구하는 문제입니다.
난이도

어려움10점 중 8점

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

문제

이차원 평면에 NN개의 선분이 있다. 다음 조건을 모두 만족하는, 가장 큰 "비어 있는" 원의 반지름을 구하는 프로그램을 작성하시오.

  1. 원의 중심은 (xc,yc)(x_c, y_c) 이다.
  2. 0≤xc≤L0 \le x_c \le L
  3. yc=0y_c = 0 (즉 중심은 xx축 위에 있다)

여기서 "비어 있는" 원이란 주어진 어떤 선분과도 교차하지 않는 원을 말한다. 단, 원이 선분에 접하는 것은 허용된다.

입력

첫째 줄에 테스트 케이스의 개수 TT가 주어진다. 각 테스트 케이스의 형식은 다음과 같다.

  • 첫째 줄에 두 정수 NN과 LL이 주어진다 (1≤N≤20001 \le N \le 2000, 0≤L≤100000 \le L \le 10000).
  • 이어지는 NN개의 줄에는 각 선분의 두 끝점을 나타내는 네 정수 xa,ya,xb,ybx_a, y_a, x_b, y_b가 순서대로 주어진다. 즉 그 선분의 양 끝점은 (xa,ya)(x_a, y_a)와 (xb,yb)(x_b, y_b)이다.

모든 좌표는 −20000-20000 이상 2000020000 이하의 정수이다.

출력

각 테스트 케이스마다 한 줄에, 가장 큰 원의 반지름을 소수점 아래 셋째 자리까지 반올림하여 출력한다.

예제1

  1. 예제 1

    입력
    1
    4 10
    1 1 10 3
    5 3 9 1
    3 1 4 1
    8 3 11 -3
    
    예상 출력
    2.118