시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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) 이다. 모든 좌표는 -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+XHVjNzc0XHVjYzI4XHVjNmQwIFx1ZDNjOVx1YmE3NFx1YzVkMCBOXHVhYzFjXHVjNzU4IFx1YzEyMFx1YmQ4NFx1Yzc3NCBcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHViMmU0XHVjNzRjIFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWJlNDRcdWM1YjRcdWM3ODhcdWIyOTQgXHVjNmQwXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPlx1YzZkMFx1Yzc1OCBcdWM5MTFcdWMyZWNcdWM3NDAgKHg8c3ViPmM8XC9zdWI+LCB5PHN1Yj5jPFwvc3ViPik8XC9saT5cclxuXHQ8bGk+MCAmbGU7IHg8c3ViPmM8XC9zdWI+ICZsZTsgTDxcL2xpPlxyXG5cdDxsaT55PHN1Yj5jPFwvc3ViPiA9IDA8XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5cdWJlNDRcdWM1YjRcdWM3ODhcdWIyOTQgXHVjNmQwXHVjNzQwIFx1YzViNFx1YjVhNCBcdWMxMjBcdWJkODRcdWFjZmNcdWIzYzQgXHVhZDUwXHVjYzI4XHVkNTU4XHVjOWMwIFx1YzU0YVx1YzU0NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YjJlOCwgXHVjODExXHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc0MCBcdWFkMWNcdWNjMmVcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YWQ2Y1x1YzEzMVx1YjQxOFx1YzViNFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVhY2ZjIExcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAyMDAwLCAwICZsZTsgTCAmbGU7IDEwMDAwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMTIwXHViZDg0XHVjNzU4IFx1YzU5MSBcdWIwNWRcdWM4MTBcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IDRcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4XHVhYzAwIHg8c3ViPmE8XC9zdWI+LCB5PHN1Yj5hPFwvc3ViPiwgeDxzdWI+YjxcL3N1Yj4sIHk8c3ViPmI8XC9zdWI+IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzk4OSwgXHVjMTIwXHViZDg0XHVjNzU4IFx1YzU5MSBcdWIwNWRcdWM4MTBcdWM3NDAgKHg8c3ViPmE8XC9zdWI+LCB5PHN1Yj5hPFwvc3ViPiksICh4PHN1Yj5iPFwvc3ViPiwgeTxzdWI+YjxcL3N1Yj4pIFx1Yzc3NFx1YjJlNC4gXHViYWE4XHViNGUwIFx1Yzg4Y1x1ZDQ1Y1x1YjI5NCAtMjAwMDBcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YWNlMCwgMjAwMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1YWMwMFx1YzdhNSBcdWQwNzAgXHVjNmQwXHVjNzU4IFx1YmMxOFx1YzljMFx1Yjk4NFx1Yzc0NCBcdWMxOGNcdWMyMThcdWM4MTAgXHVjMTRiXHVjOWY4XHVjNzkwXHViOWFjXHVhZTRjXHVjOWMwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9iaWdjLnBuZ1wiIFwvPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMzcyNiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ikxhcmdlc3QgRW1wdHkgQ2lyY2xlIG9uIGEgU2VnbWVudCIsImRlc2NyaXB0aW9uIjoiPHA+V2UgYXJlIGdpdmVuIE4gbGluZSBzZWdtZW50cyBvbiB0aGUgMkQgcGxhbmUuIFdlIHdhbnQgdG8gZmluZCB0aGUgbWF4aW11bSByYWRpdXMgb2YgYW4gZW1wdHkgY2lyY2xlIHdob3NlIGNlbnRlciBjb29yZGluYXRlcyAoeGMseWMpIGFyZSBjb25zdHJhaW5lZCBhcyBmb2xsb3dzOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjAgJmxlOyB4YyAmbGU7IEw8XC9saT5cclxuXHQ8bGk+eWMgPSAwPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+QSBjaXJjbGUgaXMgZW1wdHkgaWYgbm8gcGFydCBvZiBhIHNlZ21lbnQgaXMgbG9jYXRlZCBzdHJpY3RseSBpbnNpZGUgb2YgaXQgKHRodXMsIGEgc2VnbWVudCBtYXkgdG91Y2ggdGhlIGNpcmNsZSwgYnV0IG1heSBub3QgaW50ZXJzZWN0IHdpdGggdGhlIGludGVyaW9yIG9mIHRoZSBjaXJjbGUpPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQgZmlsZSBjb250YWlucyB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMgVC4gVGhlIHRlc3QgY2FzZXMgYXJlIGRlc2NyaWJlZCBuZXh0LiBUaGUgZmlyc3QgbGluZSBvZiBhIHRlc3QgY2FzZSBjb250YWlucyB0aGUgaW50ZWdlciBudW1iZXJzIE4gYW5kIEwgKDEgJmxlOyBOICZsZTsgMjAwMCBhbmQgMCAmbGU7IEwgJmxlOyAxMDAwMCkuIFRoZSBuZXh0IE4gbGluZXMgb2YgdGhlIHRlc3QgY2FzZSBjb250YWluIDQgaW50ZWdlcnMgZWFjaCwgZGVzY3JpYmluZyB0aGUgY29vcmRpbmF0ZXMgb2YgdGhlIGVuZHBvaW50cyBvZiBhIHNlZ21lbnQ6IHhhLCB5YSwgeGIgYW5kIHliLiBUaGUgY29vcmRpbmF0ZXMgb2YgdGhlIGVuZHBvaW50cyBvZiB0aGUgc2VnbWVudCBhcmUgKHhhLHlhKSBhbmQgKHhiLHliKS4gQWxsIHRoZSBjb29yZGluYXRlcyBhcmUgYmV0d2VlbiAtMjAwMDAgYW5kICsyMDAwMC4gRXZlcnkgdHdvIGNvbnNlY3V0aXZlIG51bWJlcnMgb24gdGhlIHNhbWUgbGluZSBhcmUgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIGJsYW5rLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSBwcmludCBhIGxpbmUgY29udGFpbmluZyBhIHJlYWwgbnVtYmVyIFIsIGRlbm90aW5nIHRoZSBtYXhpbXVtIHJhZGl1cyBvZiBhbiBlbXB0eSBjaXJjbGUgd2hvc2UgY2VudGVyIG9iZXlzIHRoZSBjb25zdHJhaW50cy4gVGhlIG51bWJlciBtdXN0IGJlIHByaW50ZWQgd2l0aCAzIGRlY2ltYWwgZGlnaXRzICh0aGUgbnVtYmVyIG11c3QgYmUgcm91bmRlZCB1cCBvciBkb3duIGFjY29yZGluZyB0byB0aGUgdXN1YWwgcm91bmRpbmcgcnVsZXMpPFwvcD5cclxuIiwiaGludCI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvYmlnYy5wbmdcIiBcLz48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

ICPC > Regionals > Europe > Southeastern European Regional Contest > SEERC 2010 C번