시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHJcblx0XHVjNzc0XHVjYzI4XHVjNmQwIFx1ZDNjOVx1YmE3NFx1YzVkMCBOXHVhYzFjXHVjNzU4IFx1YzEyMFx1YmQ4NFx1Yzc3NCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWI1NGMsIFx1YjJlNFx1Yzc0YyBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWQwNzAgXHViZTQ0XHVjNWI0XHVjNzg4XHViMjk0IFx1YzZkMFx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHA+XHJcblx0MS4gXHVjNmQwXHVjNzU4IFx1YzkxMVx1YzJlY1x1Yzc0MCAoeGMseWMpPFwvcD5cclxuPHA+XHJcblx0Mi4gMCAmbGU7IHhjICZsZTsgTDxcL3A+XHJcbjxwPlxyXG5cdDMuIHljID0gMDxcL3A+XHJcblxyXG48cD5cclxuXHRcdWJlNDRcdWM1YjRcdWM3ODhcdWIyOTQgXHVjNmQwXHVjNzQwIFx1YzViNFx1YjVhNCBcdWMxMjBcdWJkODRcdWFjZmNcdWIzYzQgXHVhZDUwXHVjYzI4XHVkNTU4XHVjOWMwIFx1YzU0YVx1YzU0NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YjJlOCwgXHVjODExXHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc0MCBcdWFkMWNcdWNjMmVcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YWQ2Y1x1YzEzMVx1YjQxOFx1YzViNFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVhY2ZjIExcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAyMDAwLCAwICZsZTsgTCAmbGU7IDEwMDAwKTxcL3A+XHJcblxyXG48cD5cclxuXHRcdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMTIwXHViZDg0XHVjNzU4IFx1YzU5MSBcdWIwNWRcdWM4MTBcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IDRcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4XHVhYzAwIHhhLCB5YSwgeGIsIHliIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzk4OSwgXHVjMTIwXHViZDg0XHVjNzU4IFx1YzU5MSBcdWIwNWRcdWM4MTBcdWM3NDAgKHhhLHlhKSwgKHhiLHliKWRcdTMxNjNcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWM4OGNcdWQ0NWNcdWIyOTQgLTIwMDAwXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM3MFx1YjA5OCBcdWFjMTlcdWFjZTAsIDIwMDAwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWM2ZDBcdWM3NTggXHViYzE4XHVjOWMwXHViOTg0XHVjNzQ0IFx1YzE4Y1x1YzIxOFx1YzgxMCBcdWMxNGJcdWM5ZjhcdWM3OTBcdWI5YWNcdWFlNGNcdWM5YzAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cclxuXHQ8aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2JpZ2MucG5nXCIgXC8+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzNzI2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTGFyZ2VzdCBFbXB0eSBDaXJjbGUgb24gYSBTZWdtZW50IiwiZGVzY3JpcHRpb24iOiI8cD5XZSBhcmUgZ2l2ZW4gTiBsaW5lIHNlZ21lbnRzIG9uIHRoZSAyRCBwbGFuZS4gV2Ugd2FudCB0byBmaW5kIHRoZSBtYXhpbXVtIHJhZGl1cyBvZiBhbiBlbXB0eSBjaXJjbGUgd2hvc2UgY2VudGVyIGNvb3JkaW5hdGVzICh4Yyx5YykgYXJlIGNvbnN0cmFpbmVkIGFzIGZvbGxvd3M6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+MCAmbGU7IHhjICZsZTsgTDxcL2xpPlxyXG5cdDxsaT55YyA9IDA8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5BIGNpcmNsZSBpcyBlbXB0eSBpZiBubyBwYXJ0IG9mIGEgc2VnbWVudCBpcyBsb2NhdGVkIHN0cmljdGx5IGluc2lkZSBvZiBpdCAodGh1cywgYSBzZWdtZW50IG1heSB0b3VjaCB0aGUgY2lyY2xlLCBidXQgbWF5IG5vdCBpbnRlcnNlY3Qgd2l0aCB0aGUgaW50ZXJpb3Igb2YgdGhlIGNpcmNsZSk8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBmaWxlIGNvbnRhaW5zIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyBULiBUaGUgdGVzdCBjYXNlcyBhcmUgZGVzY3JpYmVkIG5leHQuIFRoZSBmaXJzdCBsaW5lIG9mIGEgdGVzdCBjYXNlIGNvbnRhaW5zIHRoZSBpbnRlZ2VyIG51bWJlcnMgTiBhbmQgTCAoMSAmbGU7IE4gJmxlOyAyMDAwIGFuZCAwICZsZTsgTCAmbGU7IDEwMDAwKS4gVGhlIG5leHQgTiBsaW5lcyBvZiB0aGUgdGVzdCBjYXNlIGNvbnRhaW4gNCBpbnRlZ2VycyBlYWNoLCBkZXNjcmliaW5nIHRoZSBjb29yZGluYXRlcyBvZiB0aGUgZW5kcG9pbnRzIG9mIGEgc2VnbWVudDogeGEsIHlhLCB4YiBhbmQgeWIuIFRoZSBjb29yZGluYXRlcyBvZiB0aGUgZW5kcG9pbnRzIG9mIHRoZSBzZWdtZW50IGFyZSAoeGEseWEpIGFuZCAoeGIseWIpLiBBbGwgdGhlIGNvb3JkaW5hdGVzIGFyZSBiZXR3ZWVuIC0yMDAwMCBhbmQgKzIwMDAwLiBFdmVyeSB0d28gY29uc2VjdXRpdmUgbnVtYmVycyBvbiB0aGUgc2FtZSBsaW5lIGFyZSBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgYmxhbmsuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlIHByaW50IGEgbGluZSBjb250YWluaW5nIGEgcmVhbCBudW1iZXIgUiwgZGVub3RpbmcgdGhlIG1heGltdW0gcmFkaXVzIG9mIGFuIGVtcHR5IGNpcmNsZSB3aG9zZSBjZW50ZXIgb2JleXMgdGhlIGNvbnN0cmFpbnRzLiBUaGUgbnVtYmVyIG11c3QgYmUgcHJpbnRlZCB3aXRoIDMgZGVjaW1hbCBkaWdpdHMgKHRoZSBudW1iZXIgbXVzdCBiZSByb3VuZGVkIHVwIG9yIGRvd24gYWNjb3JkaW5nIHRvIHRoZSB1c3VhbCByb3VuZGluZyBydWxlcyk8XC9wPlxyXG4iLCJoaW50IjoiPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9iaWdjLnBuZ1wiIFwvPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d