시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHJcblx0XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1YzZkMFx1Yzc1OCBcdWJjMThcdWM5YzBcdWI5ODRcdWM3NDQgXHVjMThjXHVjMjE4XHVjODEwIFx1YzE0Ylx1YzlmOFx1Yzc5MFx1YjlhY1x1YWU0Y1x1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlxyXG5cdDxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvYmlnYy5wbmdcIiBcLz48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzcyNiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ikxhcmdlc3QgRW1wdHkgQ2lyY2xlIG9uIGEgU2VnbWVudCIsImRlc2NyaXB0aW9uIjoiPHA+V2UgYXJlIGdpdmVuIE4gbGluZSBzZWdtZW50cyBvbiB0aGUgMkQgcGxhbmUuIFdlIHdhbnQgdG8gZmluZCB0aGUgbWF4aW11bSByYWRpdXMgb2YgYW4gZW1wdHkgY2lyY2xlIHdob3NlIGNlbnRlciBjb29yZGluYXRlcyAoeGMseWMpIGFyZSBjb25zdHJhaW5lZCBhcyBmb2xsb3dzOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjAgJmxlOyB4YyAmbGU7IEw8XC9saT5cclxuXHQ8bGk+eWMgPSAwPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+QSBjaXJjbGUgaXMgZW1wdHkgaWYgbm8gcGFydCBvZiBhIHNlZ21lbnQgaXMgbG9jYXRlZCBzdHJpY3RseSBpbnNpZGUgb2YgaXQgKHRodXMsIGEgc2VnbWVudCBtYXkgdG91Y2ggdGhlIGNpcmNsZSwgYnV0IG1heSBub3QgaW50ZXJzZWN0IHdpdGggdGhlIGludGVyaW9yIG9mIHRoZSBjaXJjbGUpPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQgZmlsZSBjb250YWlucyB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMgVC4gVGhlIHRlc3QgY2FzZXMgYXJlIGRlc2NyaWJlZCBuZXh0LiBUaGUgZmlyc3QgbGluZSBvZiBhIHRlc3QgY2FzZSBjb250YWlucyB0aGUgaW50ZWdlciBudW1iZXJzIE4gYW5kIEwgKDEgJmxlOyBOICZsZTsgMjAwMCBhbmQgMCAmbGU7IEwgJmxlOyAxMDAwMCkuIFRoZSBuZXh0IE4gbGluZXMgb2YgdGhlIHRlc3QgY2FzZSBjb250YWluIDQgaW50ZWdlcnMgZWFjaCwgZGVzY3JpYmluZyB0aGUgY29vcmRpbmF0ZXMgb2YgdGhlIGVuZHBvaW50cyBvZiBhIHNlZ21lbnQ6IHhhLCB5YSwgeGIgYW5kIHliLiBUaGUgY29vcmRpbmF0ZXMgb2YgdGhlIGVuZHBvaW50cyBvZiB0aGUgc2VnbWVudCBhcmUgKHhhLHlhKSBhbmQgKHhiLHliKS4gQWxsIHRoZSBjb29yZGluYXRlcyBhcmUgYmV0d2VlbiAtMjAwMDAgYW5kICsyMDAwMC4gRXZlcnkgdHdvIGNvbnNlY3V0aXZlIG51bWJlcnMgb24gdGhlIHNhbWUgbGluZSBhcmUgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIGJsYW5rLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSBwcmludCBhIGxpbmUgY29udGFpbmluZyBhIHJlYWwgbnVtYmVyIFIsIGRlbm90aW5nIHRoZSBtYXhpbXVtIHJhZGl1cyBvZiBhbiBlbXB0eSBjaXJjbGUgd2hvc2UgY2VudGVyIG9iZXlzIHRoZSBjb25zdHJhaW50cy4gVGhlIG51bWJlciBtdXN0IGJlIHByaW50ZWQgd2l0aCAzIGRlY2ltYWwgZGlnaXRzICh0aGUgbnVtYmVyIG11c3QgYmUgcm91bmRlZCB1cCBvciBkb3duIGFjY29yZGluZyB0byB0aGUgdXN1YWwgcm91bmRpbmcgcnVsZXMpPFwvcD5cclxuIiwiaGludCI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvYmlnYy5wbmdcIiBcLz48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d