시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 124 24 19 21.111%

문제

누구나 다 아는 꿍텔레콤은 새로 건설된 고속도로에 꿍전파를 널리 퍼뜨리기 위해 여러 기지국들을 세우려고 했다. 하지만 언제나 어설픈 꿍은 발전소가 없다는 것을 뒤늦게 알아차렸다. 기지국마다 발전소를 만들 수는 없으므로 단 하나의 발전소만을 만들어 기지국들에 전력을 공급해야 한다. 이때 발전소는 고속도로상에 지을 예정이며 고속도로상의 임의의 지점에서 가장 가까운 기지국까지의 거리를 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
W3sicHJvYmxlbV9pZCI6IjMzNDYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFmY2QgXHVhZTMwXHVjOWMwXHVhZDZkIiwiZGVzY3JpcHRpb24iOiI8cD5cdWIyMDRcdWFkNmNcdWIwOTggXHViMmU0IFx1YzU0NFx1YjI5NCBcdWFmY2RcdWQxNTRcdWI4MDhcdWNmNjRcdWM3NDAgXHVjMGM4XHViODVjIFx1YWM3NFx1YzEyNFx1YjQxYyBcdWFjZTBcdWMxOGRcdWIzYzRcdWI4NWNcdWM1ZDAgXHVhZmNkXHVjODA0XHVkMzBjXHViOTdjIFx1YjExMFx1YjlhYyBcdWQzN2NcdWI3MjhcdWI5YWNcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YzVlY1x1YjdlYyBcdWFlMzBcdWM5YzBcdWFkNmRcdWI0ZTRcdWM3NDQgXHVjMTM4XHVjNmIwXHViODI0XHVhY2UwIFx1ZDU4OFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjJm5ic3A7XHVjNWI4XHVjODFjXHViMDk4IFx1YzViNFx1YzEyNFx1ZDUwOCBcdWFmY2RcdWM3NDAgXHViYzFjXHVjODA0XHVjMThjXHVhYzAwIFx1YzVjNlx1YjJlNFx1YjI5NCBcdWFjODNcdWM3NDQgXHViNGE0XHViMmE2XHVhYzhjIFx1YzU0Y1x1YzU0NFx1Y2MyOFx1YjgzOFx1YjJlNC4gXHVhZTMwXHVjOWMwXHVhZDZkXHViOWM4XHViMmU0IFx1YmMxY1x1YzgwNFx1YzE4Y1x1Yjk3YyBcdWI5Y2NcdWI0ZTQgXHVjMjE4XHViMjk0IFx1YzVjNlx1YzczY1x1YmJjMFx1Yjg1YyBcdWIyZTggXHVkNTU4XHViMDk4XHVjNzU4IFx1YmMxY1x1YzgwNFx1YzE4Y1x1YjljY1x1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWM1YjQgXHVhZTMwXHVjOWMwXHVhZDZkXHViNGU0XHVjNWQwIFx1YzgwNFx1YjgyNVx1Yzc0NCBcdWFjZjVcdWFlMDlcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWM3NzRcdWI1NGMgXHViYzFjXHVjODA0XHVjMThjXHViMjk0IFx1YWNlMFx1YzE4ZFx1YjNjNFx1Yjg1Y1x1YzBjMVx1YzVkMCBcdWM5YzBcdWM3NDQgXHVjNjA4XHVjODE1XHVjNzc0XHViYTcwIFx1YWNlMFx1YzE4ZFx1YjNjNFx1Yjg1Y1x1YzBjMVx1Yzc1OCBcdWM3ODRcdWM3NThcdWM3NTggXHVjOWMwXHVjODEwXHVjNWQwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWFjMDBcdWFlNGNcdWM2YjQgXHVhZTMwXHVjOWMwXHVhZDZkXHVhZTRjXHVjOWMwXHVjNzU4IFx1YWM3MFx1YjlhY1x1Yjk3YyBkXHViNzdjXHVhY2UwIFx1ZDU4OFx1Yzc0NCBcdWI1NGMgZFx1Yzc1OCBcdWFjMTJcdWM3NzQgXHVjZDVjXHViMzAwXHVhYzAwIFx1YjQxOFx1YjI5NCBcdWFjZjNcdWM1ZDAgXHVjOWMwXHVjNzNjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTU4XHVjOWMwXHViOWNjIFx1YWZjZFx1Yzc0MCBcdWM1YjhcdWM4MWNcdWIwOTggXHVjNWI0XHVjMTI0XHVkNTA0XHViMmU0LiBcdWM3NzRcdWJjODhcdWM1ZDBcdWIzYzQgXHVjNWVjXHViN2VjXHViZDg0XHVjNzU4IFx1YjNjNFx1YzZjMFx1Yzc3NCBcdWQ1NDRcdWM2OTRcdWQ1NThcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NTggXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM3NDAgXHViNDUwIFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMTggTigxICZsZTsgTiAmbGU7IDEwXjYpIGFuZCBMKDEgJmxlOyBMICZsZTsgMTBeOSlcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwIE5cdWM3NDAgXHVhZTMwXHVjOWMwXHVhZDZkXHVjNzU4IFx1YWMxY1x1YzIxOCwgTFx1Yzc0MCBcdWFjZTBcdWMxOGRcdWIzYzRcdWI4NWNcdWM3NTggXHVhZTM4XHVjNzc0XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE5cdWM5MDRcdWM3NDAgeGksIHlpICgtMTBeOSAmbGU7IHhpLCB5aSAmbGU7MTBeOSkgXHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljMFx1YjI5NFx1YjM3MCBcdWFjMDFcdWFjMDEgXHVhZTMwXHVjOWMwXHVhZDZkXHVjNzU4IHgsIHlcdWM4OGNcdWQ0NWNcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViYTcwIFx1YmFhOFx1YjRlMCBcdWM4MTBcdWI0ZTRcdWM3NDAgXHVjOTExXHViY2Y1XHViNDE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHVjODhjXHVkNDVjXHViNGU0XHVjNzQwIHhcdWM4OGNcdWQ0NWNcdWFjMTJcdWM3NDQgXHVhZTMwXHVjOTAwXHVjNzNjXHViODVjIFx1YzYyNFx1Yjk4NFx1Y2MyOFx1YzIxY1x1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAgXHVhYzE5XHVjNzQwIHhcdWM4OGNcdWQ0NWNcdWFjMTJcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjXHViMjk0IHlcdWM4OGNcdWQ0NWNcdWFjMTJcdWM3NDQgXHVhZTMwXHVjOTAwXHVjNzNjXHViODVjIFx1YzYyNFx1Yjk4NFx1Y2MyOFx1YzIxY1x1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWNlMFx1YzE4ZFx1YjNjNFx1Yjg1Y1x1YjI5NCAoMCwwKSBcdWJkODBcdWQxMzAgKEwsMClcdWFlNGNcdWM5YzBcdWM3NTggXHVjNzdjXHVjOWMxXHVjMTIwIFx1YjNjNFx1Yjg1Y1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5kXHVhYzEyXHViNGU0IFx1YzkxMSBcdWNkNWNcdWIzMDBcdWFjMDAgXHViNDE4XHViMjk0IFx1YWMxMiBcdWIyZTggXHVkNTU4XHViMDk4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlOCwgXHVjMThjXHVjMjE4XHVjODEwIFx1YzU0NFx1Yjc5OCAzXHVjNzkwXHViOWFjXHVhZTRjXHVjOWMwXHVjNzU4IFx1YzgxNVx1ZDY1NVx1YjNjNFx1Yjk3YyBcdWFjMDBcdWM4MzhcdWM1N2NcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzM0NiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik1vYmlsZSIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIHdlbGwta25vd24gbW9iaWxlIG5ldHdvcmsgb3BlcmF0b3IgVG90YWxwaG9uZSBoYXMgc2V0IHVwIGEgbnVtYmVyIG9mIG5ldyBiYXNlIHRyYW5zY2VpdmVyIHN0YXRpb25zIGluIG9yZGVyIHRvIGNvdmVyIGEgbmV3bHktYnVpbHQgaGlnaHdheSB3aXRoIGl0cyBuZXR3b3JrLiBBcyBhbHdheXMgdGhlIHByb2dyYW1tZXJzIG9mIFRvdGFscGhvbmUgaGF2ZSBiZWVuIHNsb3BweTsgYXMgYSByZXN1bHQsIHRoZSB0cmFuc21pc3Npb24gcG93ZXIgY2Fubm90IGJlIHNldCB1cCBpbmRpdmlkdWFsbHkgZm9yIHRoZSBzdGF0aW9ucywgYnV0IG9uZSBjYW4gb25seSBzZXQgdGhlIHRyYW5zbWlzc2lvbiBwb3dlciB0byBhIGZpeGVkIGNvbW1vbiB2YWx1ZSBmb3IgYWxsIHRoZSBzdGF0aW9ucy4gSW4gb3JkZXIgdG8gbWluaW1pemUgcG93ZXIgY29uc3VtcHRpb24sIHRoZSBjb21wYW55IHdhbnRzIHRvIGtub3cgdGhlIG1heGltYWwgZGlzdGFuY2Ugb2YgYSBwb2ludCBvbiB0aGUgaGlnaHdheSB0byB0aGUgbmVhcmVzdCBiYXNlIHRyYW5zY2VpdmVyIHN0YXRpb24uPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb25zaXN0cyBvZiB0d28gaW50ZWdlcnMgTigxICZsZTsgTiAmbGU7IDEwPHN1cD42PFwvc3VwPikgYW5kIEwoMSAmbGU7IEwgJmxlOyAxMDxzdXA+OTxcL3N1cD4pIHJlcHJlc2VudGluZyB0aGUgbnVtYmVyIG9mIGJhc2UgdHJhbnNjZWl2ZXIgc3RhdGlvbnMgYW5kIHRoZSBsZW5ndGggb2YgdGhlIGhpZ2h3YXksIHJlc3BlY3RpdmVseS4gTiBsaW5lcyBmb2xsb3csIGVhY2ggY29udGFpbmluZyBhIHBhaXIgb2YgaW50ZWdlcnMgeDxzdWI+aTxcL3N1Yj4sIHk8c3ViPmk8XC9zdWI+ICgtMTA8c3VwPjk8XC9zdXA+ICZsZTsgeDxzdWI+aTxcL3N1Yj4sIHk8c3ViPmk8XC9zdWI+ICZsZTsxMDxzdXA+OTxcL3N1cD4pIHdoaWNoIGRlc2NyaWJlcyB0aGUgY29vcmRpbmF0ZXMgb2YgYSBiYXNlIHRyYW5zY2VpdmVyIHN0YXRpb24uIEFsbCBwb2ludHMgYXJlIGRpc3RpbmN0LiBDb29yZGluYXRlcyBhcmUgc29ydGVkIGluIHRoZSBub24tZGVjcmVhc2luZyBvcmRlciB3aXRoIHJlc3BlY3QgdG8geDxzdWI+aTxcL3N1Yj4gY29vcmRpbmF0ZXMuIElmIHR3byB2YWx1ZXMgb2YgeDxzdWI+aTxcL3N1Yj4gYXJlIHRoZSBzYW1lLCB0aGVuIGNvb3JkaW5hdGVzIGFyZSBzb3J0ZWQgd2l0aCByZXNwZWN0IHRvIHk8c3ViPmk8XC9zdWI+IGNvb3JkaW5hdGVzIGluIGluY3JlYXNpbmcgb3JkZXIuPFwvcD5cclxuXHJcbjxwPlRoZSBoaWdod2F5IGlzIGEgc3RyYWlnaHQgbGluZSByYW5naW5nIGZyb20gKDA7IDApIHRvIChMOyAwKS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBzdGFuZGFyZCBvdXRwdXQgc2hvdWxkIGNvbnRhaW4gYSBzaW5nbGUgbnVtYmVyIC0gdGhlIG1heGltYWwgZGlzdGFuY2Ugb2YgYSBwb2ludCBvbiB0aGUgaGlnaHdheSB0byB0aGUgbmVhcmVzdCBiYXNlIHRyYW5zY2VpdmVyIHN0YXRpb24uIFlvdXIgb3V0cHV0IHdpbGwgYmUgcmVnYXJkZWQgYXMgY29ycmVjdCBpZiBpdCBkaWZmZXJzIGJ5IGF0IG1vc3QgMTA8c3VwPi0zPFwvc3VwPiBmcm9tIHRoZSBwcmVjaXNlIHJlc3VsdC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2012 2번

  • 문제를 번역한 사람: seok9311
  • 문제의 오타를 찾은 사람: yclock