시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 7 2 2 28.571%

문제

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

1. 원의 중심은 (xc,yc)

2. 0 ≤ xc ≤ L

3. yc = 0

비어있는 원은 어떤 선분과도 교차하지 않아야 한다. 단, 접하는 것은 괜찮다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 구성되어있다.

첫째 줄에 N과 L이 주어진다. (1 ≤ N ≤ 2000, 0 ≤ L ≤ 10000)

다음 N개의 줄에는 선분의 양 끝점을 나타내는 4개의 정수가 xa, ya, xb, yb 순서대로 주어진다. 즉, 선분의 양 끝점은 (xa,ya), (xb,yb)dㅣ다. 모든 좌표는 -20000보다 크거나 같고, 20000보다 작거나 같다.

출력

각 테스트 케이스에 대해서, 가장 큰 원의 반지름을 소수점 셋째자리까지 출력한다.

예제 입력 1

1
4 10
1 1 10 3
5 3 9 1
3 1 4 1
8 3 11 -3

예제 출력 1

2.118

힌트

W3sicHJvYmxlbV9pZCI6IjM3MjYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjMDBcdWM3YTUgXHVkMDcwIFx1YzZkMCIsImRlc2NyaXB0aW9uIjoiPHA+XHJcblx0XHVjNzc0XHVjYzI4XHVjNmQwIFx1ZDNjOVx1YmE3NFx1YzVkMCBOXHVhYzFjXHVjNzU4IFx1YzEyMFx1YmQ4NFx1Yzc3NCBcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHViMmU0XHVjNzRjIFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWJlNDRcdWM1YjRcdWM3ODhcdWIyOTQgXHVjNmQwXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG48cD5cclxuXHQxLiBcdWM2ZDBcdWM3NTggXHVjOTExXHVjMmVjXHVjNzQwICh4Yyx5Yyk8XC9wPlxyXG48cD5cclxuXHQyLiAwICZsZTsgeGMgJmxlOyBMPFwvcD5cclxuPHA+XHJcblx0My4geWMgPSAwPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YmU0NFx1YzViNFx1Yzc4OFx1YjI5NCBcdWM2ZDBcdWM3NDAgXHVjNWI0XHViNWE0IFx1YzEyMFx1YmQ4NFx1YWNmY1x1YjNjNCBcdWFkNTBcdWNjMjhcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNTQ0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViMmU4LCBcdWM4MTFcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzQwIFx1YWQxY1x1Y2MyZVx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVhZDZjXHVjMTMxXHViNDE4XHVjNWI0XHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIE5cdWFjZmMgTFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDIwMDAsIDAgJmxlOyBMICZsZTsgMTAwMDApPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjJlNFx1Yzc0YyBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMxMjBcdWJkODRcdWM3NTggXHVjNTkxIFx1YjA1ZFx1YzgxMFx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgNFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMThcdWFjMDAgeGEsIHlhLCB4YiwgeWIgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjOTg5LCBcdWMxMjBcdWJkODRcdWM3NTggXHVjNTkxIFx1YjA1ZFx1YzgxMFx1Yzc0MCAoeGEseWEpLCAoeGIseWIpZFx1MzE2M1x1YjJlNC4gXHViYWE4XHViNGUwIFx1Yzg4Y1x1ZDQ1Y1x1YjI5NCAtMjAwMDBcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YWNlMCwgMjAwMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1YzZkMFx1Yzc1OCBcdWJjMThcdWM5YzBcdWI5ODRcdWM3NDQgXHVjMThjXHVjMjE4XHVjODEwIFx1YzE0Ylx1YzlmOFx1Yzc5MFx1YjlhY1x1YWU0Y1x1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlxyXG5cdDxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvYmlnYy5wbmdcIiBcLz48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjM3MjYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJMYXJnZXN0IEVtcHR5IENpcmNsZSBvbiBhIFNlZ21lbnQiLCJkZXNjcmlwdGlvbiI6IjxwPldlIGFyZSBnaXZlbiBOIGxpbmUgc2VnbWVudHMgb24gdGhlIDJEIHBsYW5lLiBXZSB3YW50IHRvIGZpbmQgdGhlIG1heGltdW0gcmFkaXVzIG9mIGFuIGVtcHR5IGNpcmNsZSB3aG9zZSBjZW50ZXIgY29vcmRpbmF0ZXMgKHhjLHljKSBhcmUgY29uc3RyYWluZWQgYXMgZm9sbG93czo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4wICZsZTsgeGMgJmxlOyBMPFwvbGk+XHJcblx0PGxpPnljID0gMDxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkEgY2lyY2xlIGlzIGVtcHR5IGlmIG5vIHBhcnQgb2YgYSBzZWdtZW50IGlzIGxvY2F0ZWQgc3RyaWN0bHkgaW5zaWRlIG9mIGl0ICh0aHVzLCBhIHNlZ21lbnQgbWF5IHRvdWNoIHRoZSBjaXJjbGUsIGJ1dCBtYXkgbm90IGludGVyc2VjdCB3aXRoIHRoZSBpbnRlcmlvciBvZiB0aGUgY2lyY2xlKTxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGZpbGUgY29udGFpbnMgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIFQuIFRoZSB0ZXN0IGNhc2VzIGFyZSBkZXNjcmliZWQgbmV4dC4gVGhlIGZpcnN0IGxpbmUgb2YgYSB0ZXN0IGNhc2UgY29udGFpbnMgdGhlIGludGVnZXIgbnVtYmVycyBOIGFuZCBMICgxICZsZTsgTiAmbGU7IDIwMDAgYW5kIDAgJmxlOyBMICZsZTsgMTAwMDApLiBUaGUgbmV4dCBOIGxpbmVzIG9mIHRoZSB0ZXN0IGNhc2UgY29udGFpbiA0IGludGVnZXJzIGVhY2gsIGRlc2NyaWJpbmcgdGhlIGNvb3JkaW5hdGVzIG9mIHRoZSBlbmRwb2ludHMgb2YgYSBzZWdtZW50OiB4YSwgeWEsIHhiIGFuZCB5Yi4gVGhlIGNvb3JkaW5hdGVzIG9mIHRoZSBlbmRwb2ludHMgb2YgdGhlIHNlZ21lbnQgYXJlICh4YSx5YSkgYW5kICh4Yix5YikuIEFsbCB0aGUgY29vcmRpbmF0ZXMgYXJlIGJldHdlZW4gLTIwMDAwIGFuZCArMjAwMDAuIEV2ZXJ5IHR3byBjb25zZWN1dGl2ZSBudW1iZXJzIG9uIHRoZSBzYW1lIGxpbmUgYXJlIHNlcGFyYXRlZCBieSBhIHNpbmdsZSBibGFuay48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UgcHJpbnQgYSBsaW5lIGNvbnRhaW5pbmcgYSByZWFsIG51bWJlciBSLCBkZW5vdGluZyB0aGUgbWF4aW11bSByYWRpdXMgb2YgYW4gZW1wdHkgY2lyY2xlIHdob3NlIGNlbnRlciBvYmV5cyB0aGUgY29uc3RyYWludHMuIFRoZSBudW1iZXIgbXVzdCBiZSBwcmludGVkIHdpdGggMyBkZWNpbWFsIGRpZ2l0cyAodGhlIG51bWJlciBtdXN0IGJlIHJvdW5kZWQgdXAgb3IgZG93biBhY2NvcmRpbmcgdG8gdGhlIHVzdWFsIHJvdW5kaW5nIHJ1bGVzKTxcL3A+XHJcbiIsImhpbnQiOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2JpZ2MucG5nXCIgXC8+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=