시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 102 17 13 18.841%

문제

누구나 다 아는 꿍텔레콤은 새로 건설된 고속도로에 꿍전파를 널리 퍼뜨리기 위해 여러 기지국들을 세우려고 했다. 하지만 언제나 어설픈 꿍은 발전소가 없다는 것을 뒤늦게 알아차렸다. 기지국마다 발전소를 만들수는 없으므로 단 하나의 발전소만을 만들어 기지국들에 전력을 공급해야 한다. 이때 발전소는 고속도로상에 지을 예정이며 고속도로상의 임의의 지점에서 가장 가까운 발전소까지의 거리를 d라고 했을 때 d의 값이 최대가 되는 곳에 지으려고 한다.

하지만 꿍은 언제나 어설프다. 이번에도 여러분의 도움이 필요하다.

입력

입력의 첫번째 줄은 두 개의 정수 N(1 ≤ N ≤ 10^6) and L(1 ≤ L ≤ 10^9)가 주어지며 N은 기지국의 개수, L은 고속도로의 길이를 나타낸다.

다음 N줄은 xi, yi (-10^9 ≤ xi, yi ≤10^9) 으로 이루어지는데 각각 기지국의 x, y좌표를 나타내며 모든 점들은 중복되지 않는다. 좌표들은 x좌표값을 기준으로 오름차순으로 주어지며 같은 x좌표값에 대해서는 y좌표값을 기준으로 오름차순으로 주어진다.

고속도로는 (0,0) 부터 (L,0)까지의 일직선 도로다.

출력

d값들 중 최대가 되는 값 단 하나를 출력하면 된다.

단, 소수점 아래 3자리까지의 정확도를 가져야한다.

예제 입력 1

2 10
0 0
11 1

예제 출력 1

5.545455

힌트

W3sicHJvYmxlbV9pZCI6IjMzNDYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFmY2QgXHVhZTMwXHVjOWMwXHVhZDZkIiwiZGVzY3JpcHRpb24iOiI8cD5cdWIyMDRcdWFkNmNcdWIwOTggXHViMmU0IFx1YzU0NFx1YjI5NCBcdWFmY2RcdWQxNTRcdWI4MDhcdWNmNjRcdWM3NDAgXHVjMGM4XHViODVjIFx1YWM3NFx1YzEyNFx1YjQxYyBcdWFjZTBcdWMxOGRcdWIzYzRcdWI4NWNcdWM1ZDAgXHVhZmNkXHVjODA0XHVkMzBjXHViOTdjIFx1YjExMFx1YjlhYyBcdWQzN2NcdWI3MjhcdWI5YWNcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YzVlY1x1YjdlYyBcdWFlMzBcdWM5YzBcdWFkNmRcdWI0ZTRcdWM3NDQgXHVjMTM4XHVjNmIwXHViODI0XHVhY2UwIFx1ZDU4OFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjJm5ic3A7XHVjNWI4XHVjODFjXHViMDk4IFx1YzViNFx1YzEyNFx1ZDUwOCBcdWFmY2RcdWM3NDAgXHViYzFjXHVjODA0XHVjMThjXHVhYzAwIFx1YzVjNlx1YjJlNFx1YjI5NCBcdWFjODNcdWM3NDQgXHViNGE0XHViMmE2XHVhYzhjIFx1YzU0Y1x1YzU0NFx1Y2MyOFx1YjgzOFx1YjJlNC4gXHVhZTMwXHVjOWMwXHVhZDZkXHViOWM4XHViMmU0IFx1YmMxY1x1YzgwNFx1YzE4Y1x1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWMyMThcdWIyOTQgXHVjNWM2XHVjNzNjXHViYmMwXHViODVjIFx1YjJlOCBcdWQ1NThcdWIwOThcdWM3NTggXHViYzFjXHVjODA0XHVjMThjXHViOWNjXHVjNzQ0IFx1YjljY1x1YjRlNFx1YzViNCBcdWFlMzBcdWM5YzBcdWFkNmRcdWI0ZTRcdWM1ZDAgXHVjODA0XHViODI1XHVjNzQ0IFx1YWNmNVx1YWUwOVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YjU0YyBcdWJjMWNcdWM4MDRcdWMxOGNcdWIyOTQgXHVhY2UwXHVjMThkXHViM2M0XHViODVjXHVjMGMxXHVjNWQwIFx1YzljMFx1Yzc0NCBcdWM2MDhcdWM4MTVcdWM3NzRcdWJhNzAgXHVhY2UwXHVjMThkXHViM2M0XHViODVjXHVjMGMxXHVjNzU4IFx1Yzc4NFx1Yzc1OFx1Yzc1OCBcdWM5YzBcdWM4MTBcdWM1ZDBcdWMxMWMgXHVhYzAwXHVjN2E1IFx1YWMwMFx1YWU0Y1x1YzZiNCBcdWJjMWNcdWM4MDRcdWMxOGNcdWFlNGNcdWM5YzBcdWM3NTggXHVhYzcwXHViOWFjXHViOTdjIGRcdWI3N2NcdWFjZTAgXHVkNTg4XHVjNzQ0IFx1YjU0YyBkXHVjNzU4IFx1YWMxMlx1Yzc3NCBcdWNkNWNcdWIzMDBcdWFjMDAgXHViNDE4XHViMjk0IFx1YWNmM1x1YzVkMCBcdWM5YzBcdWM3M2NcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ1NThcdWM5YzBcdWI5Y2MgXHVhZmNkXHVjNzQwIFx1YzViOFx1YzgxY1x1YjA5OCBcdWM1YjRcdWMxMjRcdWQ1MDRcdWIyZTQuIFx1Yzc3NFx1YmM4OFx1YzVkMFx1YjNjNCBcdWM1ZWNcdWI3ZWNcdWJkODRcdWM3NTggXHViM2M0XHVjNmMwXHVjNzc0IFx1ZDU0NFx1YzY5NFx1ZDU1OFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWNjYWJcdWJjODhcdWM5ZjggXHVjOTA0XHVjNzQwIFx1YjQ1MCBcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4IE4oMSAmbGU7IE4gJmxlOyAxMF42KSBhbmQgTCgxICZsZTsgTCAmbGU7IDEwXjkpXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCBOXHVjNzQwIFx1YWUzMFx1YzljMFx1YWQ2ZFx1Yzc1OCBcdWFjMWNcdWMyMTgsIExcdWM3NDAgXHVhY2UwXHVjMThkXHViM2M0XHViODVjXHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBOXHVjOTA0XHVjNzQwIHhpLCB5aSAoLTEwXjkgJmxlOyB4aSwgeWkgJmxlOzEwXjkpIFx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzBcdWIyOTRcdWIzNzAgXHVhYzAxXHVhYzAxIFx1YWUzMFx1YzljMFx1YWQ2ZFx1Yzc1OCB4LCB5XHVjODhjXHVkNDVjXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YmE3MCBcdWJhYThcdWI0ZTAgXHVjODEwXHViNGU0XHVjNzQwIFx1YzkxMVx1YmNmNVx1YjQxOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuIFx1Yzg4Y1x1ZDQ1Y1x1YjRlNFx1Yzc0MCB4XHVjODhjXHVkNDVjXHVhYzEyXHVjNzQ0IFx1YWUzMFx1YzkwMFx1YzczY1x1Yjg1YyBcdWM2MjRcdWI5ODRcdWNjMjhcdWMyMWNcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwIFx1YWMxOVx1Yzc0MCB4XHVjODhjXHVkNDVjXHVhYzEyXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExY1x1YjI5NCB5XHVjODhjXHVkNDVjXHVhYzEyXHVjNzQ0IFx1YWUzMFx1YzkwMFx1YzczY1x1Yjg1YyBcdWM2MjRcdWI5ODRcdWNjMjhcdWMyMWNcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjZTBcdWMxOGRcdWIzYzRcdWI4NWNcdWIyOTQgKDAsMCkgXHViZDgwXHVkMTMwIChMLDApXHVhZTRjXHVjOWMwXHVjNzU4IFx1Yzc3Y1x1YzljMVx1YzEyMCBcdWIzYzRcdWI4NWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+ZFx1YWMxMlx1YjRlNCBcdWM5MTEgXHVjZDVjXHViMzAwXHVhYzAwIFx1YjQxOFx1YjI5NCBcdWFjMTIgXHViMmU4IFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWJhNzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTgsIFx1YzE4Y1x1YzIxOFx1YzgxMCBcdWM1NDRcdWI3OTggM1x1Yzc5MFx1YjlhY1x1YWU0Y1x1YzljMFx1Yzc1OCBcdWM4MTVcdWQ2NTVcdWIzYzRcdWI5N2MgXHVhYzAwXHVjODM4XHVjNTdjXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMzNDYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJNb2JpbGUiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSB3ZWxsLWtub3duIG1vYmlsZSBuZXR3b3JrIG9wZXJhdG9yIFRvdGFscGhvbmUgaGFzIHNldCB1cCBhIG51bWJlciBvZiBuZXcgYmFzZSB0cmFuc2NlaXZlciBzdGF0aW9ucyBpbiBvcmRlciB0byBjb3ZlciBhIG5ld2x5LWJ1aWx0IGhpZ2h3YXkgd2l0aCBpdHMgbmV0d29yay4gQXMgYWx3YXlzIHRoZSBwcm9ncmFtbWVycyBvZiBUb3RhbHBob25lIGhhdmUgYmVlbiBzbG9wcHk7IGFzIGEgcmVzdWx0LCB0aGUgdHJhbnNtaXNzaW9uIHBvd2VyIGNhbm5vdCBiZSBzZXQgdXAgaW5kaXZpZHVhbGx5IGZvciB0aGUgc3RhdGlvbnMsIGJ1dCBvbmUgY2FuIG9ubHkgc2V0IHRoZSB0cmFuc21pc3Npb24gcG93ZXIgdG8gYSBmaXhlZCBjb21tb24gdmFsdWUgZm9yIGFsbCB0aGUgc3RhdGlvbnMuIEluIG9yZGVyIHRvIG1pbmltaXplIHBvd2VyIGNvbnN1bXB0aW9uLCB0aGUgY29tcGFueSB3YW50cyB0byBrbm93IHRoZSBtYXhpbWFsIGRpc3RhbmNlIG9mIGEgcG9pbnQgb24gdGhlIGhpZ2h3YXkgdG8gdGhlIG5lYXJlc3QgYmFzZSB0cmFuc2NlaXZlciBzdGF0aW9uLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGV4dCBmaWxlIG1vYmlsZS5pbiBjb25zaXN0cyBvZiB0d28gaW50ZWdlcnMgTigxICZsZTsgTiAmbGU7IDEwPHN1cD42PFwvc3VwPikgYW5kIEwoMSAmbGU7IEwgJmxlOyAxMDxzdXA+OTxcL3N1cD4pIHJlcHJlc2VudGluZyB0aGUgbnVtYmVyIG9mIGJhc2UgdHJhbnNjZWl2ZXIgc3RhdGlvbnMgYW5kIHRoZSBsZW5ndGggb2YgdGhlIGhpZ2h3YXksIHJlc3BlY3RpdmVseS4gTiBsaW5lcyBmb2xsb3csIGVhY2ggY29udGFpbmluZyBhIHBhaXIgb2YgaW50ZWdlcnMgeDxzdWI+aTxcL3N1Yj4sIHk8c3ViPmk8XC9zdWI+ICgtMTA8c3VwPjk8XC9zdXA+ICZsZTsgeDxzdWI+aTxcL3N1Yj4sIHk8c3ViPmk8XC9zdWI+ICZsZTsxMDxzdXA+OTxcL3N1cD4pIHdoaWNoIGRlc2NyaWJlcyB0aGUgY29vcmRpbmF0ZXMgb2YgYSBiYXNlIHRyYW5zY2VpdmVyIHN0YXRpb24uIEFsbCBwb2ludHMgYXJlIGRpc3RpbmN0LiBDb29yZGluYXRlcyBhcmUgc29ydGVkIGluIHRoZSBub24tZGVjcmVhc2luZyBvcmRlciB3aXRoIHJlc3BlY3QgdG8geDxzdWI+aTxcL3N1Yj4gY29vcmRpbmF0ZXMuIElmIHR3byB2YWx1ZXMgb2YgeDxzdWI+aTxcL3N1Yj4gYXJlIHRoZSBzYW1lLCB0aGVuIGNvb3JkaW5hdGVzIGFyZSBzb3J0ZWQgd2l0aCByZXNwZWN0IHRvIHk8c3ViPmk8XC9zdWI+IGNvb3JkaW5hdGVzIGluIGluY3JlYXNpbmcgb3JkZXIuPFwvcD5cclxuXHJcbjxwPlRoZSBoaWdod2F5IGlzIGEgc3RyYWlnaHQgbGluZSByYW5naW5nIGZyb20gKDA7IDApIHRvIChMOyAwKS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiB0aGUgdGV4dCBmaWxlIG1vYmlsZS5vdXQgc2hvdWxkIGNvbnRhaW4gYSBzaW5nbGUgbnVtYmVyIC0gdGhlIG1heGltYWwgZGlzdGFuY2Ugb2YgYSBwb2ludCBvbiB0aGUgaGlnaHdheSB0byB0aGUgbmVhcmVzdCBiYXNlIHRyYW5zY2VpdmVyIHN0YXRpb24uIFlvdXIgb3V0cHV0IHdpbGwgYmUgcmVnYXJkZWQgYXMgY29ycmVjdCBpZiBpdCBkaWZmZXJzIGJ5IGF0IG1vc3QgMTA8c3VwPi0zPFwvc3VwPiBmcm9tIHRoZSBwcmVjaXNlIHJlc3VsdC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2012 2번