시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB35151150.000%

문제

크기가 m×n인 복도가 있다. 이 복도에는 크기를 무시할 있는 기둥이 여러 개 있다. 복도를 서쪽에서 동쪽까지 통과할 수 있는 가장 큰 공을 구하는 프로그램을 작성하시오. 공은 완전한 구 모양이어야 한다. 또, 서쪽의 아무 위치에서나 시작할 수 있고, 가장 동쪽의 아무데서나 도착하면 된다. 복도의 높이는 매우 높기 때문에, 공이 천장에 닿는 경우는 없다. 

입력

첫째 줄에 복도의 가로길이 m과 세로길이 n이 주어진다. 다음 줄에는 복도에 있는 기둥의 수 k가 주어진다. 다음 k개 줄에는 복도의 좌표가 한 줄에 하나씩 주어진다. (0 ≤ n,m,k ≤ 1000) 첫 번째 좌표가 가로 방향의 좌표이다.

가로 방향이 서쪽에서 동쪽으로 향하는 방향이며, 세로 방향은 남쪽에서 북쪽으로 향하는 방향이다. 즉, 가로 방향의 가장 왼쪽이 서쪽이 되고, 가장 오른쪽이 동쪽이 된다.

출력

첫째 줄에 복도를 통과할 수 있는 가장 큰 공의 반지름을 소수점 여덟째 자리까지 출력한다.

예제 입력 1

5 2
1
1 1

예제 출력 1

0.50000000
W3sicHJvYmxlbV9pZCI6Ijc3ODgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjZjVcdWIzYzQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDA2Y1x1YWUzMFx1YWMwMCBtJnRpbWVzO25cdWM3NzggXHViY2Y1XHViM2M0XHVhYzAwIFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1YmNmNVx1YjNjNFx1YzVkMFx1YjI5NCBcdWQwNmNcdWFlMzBcdWI5N2MgXHViYjM0XHVjMmRjXHVkNTYwIFx1Yzc4OFx1YjI5NCBcdWFlMzBcdWI0NjVcdWM3NzQgXHVjNWVjXHViN2VjIFx1YWMxYyBcdWM3ODhcdWIyZTQuIFx1YmNmNVx1YjNjNFx1Yjk3YyBcdWMxMWNcdWNhYmRcdWM1ZDBcdWMxMWMgXHViM2Q5XHVjYWJkXHVhZTRjXHVjOWMwIFx1ZDFiNVx1YWNmY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWQwNzAgXHVhY2Y1XHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWFjZjVcdWM3NDAgXHVjNjQ0XHVjODA0XHVkNTVjIFx1YWQ2YyBcdWJhYThcdWM1OTFcdWM3NzRcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWI2MTAsIFx1YzExY1x1Y2FiZFx1Yzc1OCBcdWM1NDRcdWJiMzQgXHVjNzA0XHVjZTU4XHVjNWQwXHVjMTFjXHViMDk4IFx1YzJkY1x1Yzc5MVx1ZDU2MCBcdWMyMTggXHVjNzg4XHVhY2UwLCBcdWFjMDBcdWM3YTUgXHViM2Q5XHVjYWJkXHVjNzU4IFx1YzU0NFx1YmIzNFx1YjM3MFx1YzExY1x1YjA5OCBcdWIzYzRcdWNjMjlcdWQ1NThcdWJhNzQgXHViNDFjXHViMmU0LiBcdWJjZjVcdWIzYzRcdWM3NTggXHViMTkyXHVjNzc0XHViMjk0IFx1YjllNFx1YzZiMCBcdWIxOTJcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWFjZjVcdWM3NzQgXHVjYzljXHVjN2E1XHVjNWQwIFx1YjJmZlx1YjI5NCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNWM2XHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJjZjVcdWIzYzRcdWM3NTggXHVhYzAwXHViODVjXHVhZTM4XHVjNzc0IG1cdWFjZmMgXHVjMTM4XHViODVjXHVhZTM4XHVjNzc0IG5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YmNmNVx1YjNjNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVhZTMwXHViNDY1XHVjNzU4IFx1YzIxOCBrXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIGtcdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YmNmNVx1YjNjNFx1Yzc1OCBcdWM4OGNcdWQ0NWNcdWFjMDAgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMCAmbGU7IG4sbSxrICZsZTsgMTAwMCkgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM4OGNcdWQ0NWNcdWFjMDAgXHVhYzAwXHViODVjJm5ic3A7XHViYzI5XHVkNWE1XHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAwXHViODVjIFx1YmMyOVx1ZDVhNVx1Yzc3NCBcdWMxMWNcdWNhYmRcdWM1ZDBcdWMxMWMgXHViM2Q5XHVjYWJkXHVjNzNjXHViODVjIFx1ZDVhNVx1ZDU1OFx1YjI5NCBcdWJjMjlcdWQ1YTVcdWM3NzRcdWJhNzAsIFx1YzEzOFx1Yjg1YyBcdWJjMjlcdWQ1YTVcdWM3NDAgXHViMGE4XHVjYWJkXHVjNWQwXHVjMTFjIFx1YmQ4MVx1Y2FiZFx1YzczY1x1Yjg1YyBcdWQ1YTVcdWQ1NThcdWIyOTQgXHViYzI5XHVkNWE1XHVjNzc0XHViMmU0LiBcdWM5ODksIFx1YWMwMFx1Yjg1YyBcdWJjMjlcdWQ1YTVcdWM3NTggXHVhYzAwXHVjN2E1IFx1YzY3Y1x1Y2FiZFx1Yzc3NCBcdWMxMWNcdWNhYmRcdWM3NzQgXHViNDE4XHVhY2UwLCBcdWFjMDBcdWM3YTUgXHVjNjI0XHViOTc4XHVjYWJkXHVjNzc0IFx1YjNkOVx1Y2FiZFx1Yzc3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJjZjVcdWIzYzRcdWI5N2MgXHVkMWI1XHVhY2ZjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWFjZjVcdWM3NTggXHViYzE4XHVjOWMwXHViOTg0XHVjNzQ0IFx1YzE4Y1x1YzIxOFx1YzgxMCBcdWM1ZWNcdWIzNWZcdWM5ZjggXHVjNzkwXHViOWFjXHVhZTRjXHVjOWMwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI3Nzg4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiSGFsbHdheSIsImRlc2NyaXB0aW9uIjoiPHA+Q29uc2lkZXIgYSByZWN0YW5ndWxhciBoYWxsd2F5IG9mIHNpemUgbXhuLiBJbiB0aGlzIGhhbGx3YXkgdGhlcmUgYXJlIHNldmVyYWwgcGlsbGFycyBoYXZpbmcgYSBuZWdsaWdpYmxlIHNpemUuIFlvdSBoYXZlIHRvIGNvbXB1dGUgdGhlIG1heGltdW0gcmFkaXVzIG9mIGEgc3BoZXJpY2FsIGJhbGwgd2hpY2ggbWF5IHBhc3MgdGhyb3VnaCB0aGUgaGFsbHdheSBmcm9tIHRoZSB3ZXN0IGVuZCB0byB0aGUgZWFzdCBlbmQuIFRoZSBiYWxsIG1heSBzdGFydCBmcm9tIGFueSBwb3NpdGlvbiBvbiB0aGUgd2VzdCBlbmQgYW5kIG1heSBhcnJpdmUgYXQgYW55IHBvc2l0aW9uIG9uIHRoZSBlYXN0IGVuZC4gVGhlIGhhbGx3YXkgaXMgYWx3YXlzIGhpZ2ggZW5vdWdoPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgXHVmYjAxbGUgY29udGFpbnMgb24gdGhlIFx1ZmIwMXJzdCBsaW5lIHR3byBpbnRlZ2VycyBtIGFuZCBuLCBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgYmxhbmsgY2hhcmFjdGVyLCByZXByZXNlbnRpbmcgdGhlIGRpbWVuc2lvbnMgb2YgdGhlIGhhbGx3YXkgb24gdGhlIGVhc3Qtd2VzdCBhbmQgbm9ydGgtc291dGggZGlyZWN0aW9ucywgcmVzcGVjdGl2ZWx5LiBUaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgYSBzaW5nbGUgaW50ZWdlciBrIHJlcHJlc2VudGluZyB0aGUgbnVtYmVyIG9mIHBpbGxhcnMgaW4gdGhlIGhhbGx3YXkuIEVhY2ggb2YgdGhlIGZvbGxvd2luZyBrIGxpbmVzIGNvbnRhaW5zIHR3byBpbnRlZ2Vycywgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIGJsYW5rIGNoYXJhY3RlciwgcmVwcmVzZW50aW5nIHRoZSBjb29yZGluYXRlcyBvZiBhIHBpbGxhci4gSXQgaXMgZ3VhcmFudGVlZCB0aGF0IDAgJmxlOyBuLG0sayAmbGU7IDEwMDAuPFwvcD5cclxuXHJcbjxwPlRoZSBlYXN0LXdlc3QgZGlyZWN0aW9uIGlzIHJlcHJlc2VudGVkIGJ5IHRoZSBcdWZiMDFyc3QgY29vcmRpbmF0ZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgb3V0cHV0IFx1ZmIwMWxlIG11c3QgY29udGFpbiBhIHNpbmdsZSBudW1iZXIsIHJlcHJlc2VudGluZyB0aGUgcmFkaXVzIG9mIHRoZSBsYXJnZXN0IHNwaGVyaWNhbCBiYWxsIHdoaWNoIG1heSBwYXNzIHRocm91Z2ggdGhlIGhhbGx3YXkgZnJvbSB0aGUgd2VzdCBlbmQgdG8gdGhlIGVhc3QgZW5kLjxcL3A+XHJcblxyXG48cD5UaGUgcmFkaXVzIG9mIHRoZSBkZXRlcm1pbmVkIGJhbGwgbXVzdCBiZSB3cml0dGVuIHVzaW5nIGV4YWN0bHkgZWlnaHQgZGlnaXRzIGFmdGVyIHRoZSBkZWNpbWFsIHBvaW50LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Contest > KBTU Open > KBTU Open 2008 H번