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

문제

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

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

입력

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

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

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

출력

가능한 d의 최댓값을 출력한다. 절대오차는 $10^{-3}$까지 허용한다.

예제 입력 1

2 10
0 0
11 1

예제 출력 1

5.545455
W3sicHJvYmxlbV9pZCI6IjMzNDYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFmY2QgXHVhZTMwXHVjOWMwXHVhZDZkIiwiZGVzY3JpcHRpb24iOiI8cD5cdWIyMDRcdWFkNmNcdWIwOTggXHViMmU0IFx1YzU0NFx1YjI5NCBcdWFmY2RcdWQxNTRcdWI4MDhcdWNmNjRcdWM3NDAgXHVjMGM4XHViODVjIFx1YWM3NFx1YzEyNFx1YjQxYyBcdWFjZTBcdWMxOGRcdWIzYzRcdWI4NWNcdWM1ZDAgXHVhZmNkXHVjODA0XHVkMzBjXHViOTdjIFx1YjExMFx1YjlhYyBcdWQzN2NcdWI3MjhcdWI5YWNcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YzVlY1x1YjdlYyBcdWFlMzBcdWM5YzBcdWFkNmRcdWI0ZTRcdWM3NDQgXHVjMTM4XHVjNmIwXHViODI0XHVhY2UwIFx1ZDU4OFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjIFx1YzViOFx1YzgxY1x1YjA5OCBcdWM1YjRcdWMxMjRcdWQ1MDggXHVhZmNkXHVjNzQwIFx1YmMxY1x1YzgwNFx1YzE4Y1x1YWMwMCBcdWM1YzZcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YjRhNFx1YjJhNlx1YWM4YyBcdWM1NGNcdWM1NDRcdWNjMjhcdWI4MzhcdWIyZTQuIFx1YWUzMFx1YzljMFx1YWQ2ZFx1YjljOFx1YjJlNCBcdWJjMWNcdWM4MDRcdWMxOGNcdWI5N2MgXHViOWNjXHViNGU0IFx1YzIxOFx1YjI5NCBcdWM1YzZcdWM3M2NcdWJiYzBcdWI4NWMgXHViMmU4IFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWJjMWNcdWM4MDRcdWMxOGNcdWI5Y2NcdWM3NDQgXHViOWNjXHViNGU0XHVjNWI0IFx1YWUzMFx1YzljMFx1YWQ2ZFx1YjRlNFx1YzVkMCBcdWM4MDRcdWI4MjVcdWM3NDQgXHVhY2Y1XHVhZTA5XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVjNzc0XHViNTRjIFx1YmMxY1x1YzgwNFx1YzE4Y1x1YjI5NCBcdWFjZTBcdWMxOGRcdWIzYzRcdWI4NWNcdWMwYzFcdWM1ZDAgXHVjOWMwXHVjNzQ0IFx1YzYwOFx1YzgxNVx1Yzc3NFx1YmE3MCBcdWFjZTBcdWMxOGRcdWIzYzRcdWI4NWNcdWMwYzFcdWM3NTggXHVjNzg0XHVjNzU4XHVjNzU4IFx1YzljMFx1YzgxMFx1YzVkMFx1YzExYyBcdWFjMDBcdWM3YTUgXHVhYzAwXHVhZTRjXHVjNmI0IFx1YWUzMFx1YzljMFx1YWQ2ZFx1YWU0Y1x1YzljMFx1Yzc1OCBcdWFjNzBcdWI5YWNcdWI5N2MgZFx1Yjc3Y1x1YWNlMCBcdWQ1ODhcdWM3NDQgXHViNTRjIGRcdWM3NTggXHVhYzEyXHVjNzc0IFx1Y2Q1Y1x1YjMwMFx1YWMwMCBcdWI0MThcdWIyOTQgXHVhY2YzXHVjNWQwIFx1YzljMFx1YzczY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDU1OFx1YzljMFx1YjljYyBcdWFmY2RcdWM3NDAgXHVjNWI4XHVjODFjXHViMDk4IFx1YzViNFx1YzEyNFx1ZDUwNFx1YjJlNC4gXHVjNzc0XHViYzg4XHVjNWQwXHViM2M0IFx1YzVlY1x1YjdlY1x1YmQ4NFx1Yzc1OCBcdWIzYzRcdWM2YzBcdWM3NzQgXHVkNTQ0XHVjNjk0XHVkNTU4XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNzQwIFx1YjQ1MCBcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4ICROJCAoJDEgJmxlOyBOICZsZTsgMTBeNiQpIGFuZCAkTCQgKCQxICZsZTsgTCAmbGU7IDEwXjkkKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAgJE4kXHVjNzQwIFx1YWUzMFx1YzljMFx1YWQ2ZFx1Yzc1OCBcdWFjMWNcdWMyMTgsICRMJFx1Yzc0MCBcdWFjZTBcdWMxOGRcdWIzYzRcdWI4NWNcdWM3NTggXHVhZTM4XHVjNzc0XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjICROJFx1YzkwNFx1Yzc0MCAkeF9pJCwgJHlfaSQgKCQtMTBeOSAmbGU7IHhfaSwgeV9pICZsZTsxMF45JCkgXHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljMFx1YjI5NFx1YjM3MCBcdWFjMDFcdWFjMDEgXHVhZTMwXHVjOWMwXHVhZDZkXHVjNzU4ICR4JCwgJHkkXHVjODhjXHVkNDVjXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YmE3MCBcdWJhYThcdWI0ZTAgXHVjODEwXHViNGU0XHVjNzQwIFx1YzkxMVx1YmNmNVx1YjQxOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuIFx1Yzg4Y1x1ZDQ1Y1x1YjRlNFx1Yzc0MCAkeCRcdWM4OGNcdWQ0NWNcdWFjMTJcdWM3NDQgXHVhZTMwXHVjOTAwXHVjNzNjXHViODVjIFx1YzYyNFx1Yjk4NFx1Y2MyOFx1YzIxY1x1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAgXHVhYzE5XHVjNzQwICR4JFx1Yzg4Y1x1ZDQ1Y1x1YWMxMlx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWNcdWIyOTQgJHkkXHVjODhjXHVkNDVjXHVhYzEyXHVjNzQ0IFx1YWUzMFx1YzkwMFx1YzczY1x1Yjg1YyBcdWM2MjRcdWI5ODRcdWNjMjhcdWMyMWNcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjZTBcdWMxOGRcdWIzYzRcdWI4NWNcdWIyOTQgJCgwLDApJCBcdWJkODBcdWQxMzAgJChMLDApJFx1YWU0Y1x1YzljMFx1Yzc1OCBcdWM3N2NcdWM5YzFcdWMxMjAgXHViM2M0XHViODVjXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMFx1YjJhNVx1ZDU1YyBkXHVjNzU4IFx1Y2Q1Y1x1YjMxM1x1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YzgwOFx1YjMwMFx1YzYyNFx1Y2MyOFx1YjI5NCAkMTBeey0zfSRcdWFlNGNcdWM5YzAgXHVkNWM4XHVjNmE5XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjMzNDYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJNb2JpbGUiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSB3ZWxsLWtub3duIG1vYmlsZSBuZXR3b3JrIG9wZXJhdG9yIFRvdGFscGhvbmUgaGFzIHNldCB1cCBhIG51bWJlciBvZiBuZXcgYmFzZSB0cmFuc2NlaXZlciBzdGF0aW9ucyBpbiBvcmRlciB0byBjb3ZlciBhIG5ld2x5LWJ1aWx0IGhpZ2h3YXkgd2l0aCBpdHMgbmV0d29yay4gQXMgYWx3YXlzIHRoZSBwcm9ncmFtbWVycyBvZiBUb3RhbHBob25lIGhhdmUgYmVlbiBzbG9wcHk7IGFzIGEgcmVzdWx0LCB0aGUgdHJhbnNtaXNzaW9uIHBvd2VyIGNhbm5vdCBiZSBzZXQgdXAgaW5kaXZpZHVhbGx5IGZvciB0aGUgc3RhdGlvbnMsIGJ1dCBvbmUgY2FuIG9ubHkgc2V0IHRoZSB0cmFuc21pc3Npb24gcG93ZXIgdG8gYSBmaXhlZCBjb21tb24gdmFsdWUgZm9yIGFsbCB0aGUgc3RhdGlvbnMuIEluIG9yZGVyIHRvIG1pbmltaXplIHBvd2VyIGNvbnN1bXB0aW9uLCB0aGUgY29tcGFueSB3YW50cyB0byBrbm93IHRoZSBtYXhpbWFsIGRpc3RhbmNlIG9mIGEgcG9pbnQgb24gdGhlIGhpZ2h3YXkgdG8gdGhlIG5lYXJlc3QgYmFzZSB0cmFuc2NlaXZlciBzdGF0aW9uLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29uc2lzdHMgb2YgdHdvIGludGVnZXJzIE4oMSAmbGU7IE4gJmxlOyAxMDxzdXA+NjxcL3N1cD4pIGFuZCBMKDEgJmxlOyBMICZsZTsgMTA8c3VwPjk8XC9zdXA+KSByZXByZXNlbnRpbmcgdGhlIG51bWJlciBvZiBiYXNlIHRyYW5zY2VpdmVyIHN0YXRpb25zIGFuZCB0aGUgbGVuZ3RoIG9mIHRoZSBoaWdod2F5LCByZXNwZWN0aXZlbHkuIE4gbGluZXMgZm9sbG93LCBlYWNoIGNvbnRhaW5pbmcgYSBwYWlyIG9mIGludGVnZXJzIHg8c3ViPmk8XC9zdWI+LCB5PHN1Yj5pPFwvc3ViPiAoLTEwPHN1cD45PFwvc3VwPiAmbGU7IHg8c3ViPmk8XC9zdWI+LCB5PHN1Yj5pPFwvc3ViPiAmbGU7MTA8c3VwPjk8XC9zdXA+KSB3aGljaCBkZXNjcmliZXMgdGhlIGNvb3JkaW5hdGVzIG9mIGEgYmFzZSB0cmFuc2NlaXZlciBzdGF0aW9uLiBBbGwgcG9pbnRzIGFyZSBkaXN0aW5jdC4gQ29vcmRpbmF0ZXMgYXJlIHNvcnRlZCBpbiB0aGUgbm9uLWRlY3JlYXNpbmcgb3JkZXIgd2l0aCByZXNwZWN0IHRvIHg8c3ViPmk8XC9zdWI+IGNvb3JkaW5hdGVzLiBJZiB0d28gdmFsdWVzIG9mIHg8c3ViPmk8XC9zdWI+IGFyZSB0aGUgc2FtZSwgdGhlbiBjb29yZGluYXRlcyBhcmUgc29ydGVkIHdpdGggcmVzcGVjdCB0byB5PHN1Yj5pPFwvc3ViPiBjb29yZGluYXRlcyBpbiBpbmNyZWFzaW5nIG9yZGVyLjxcL3A+XHJcblxyXG48cD5UaGUgaGlnaHdheSBpcyBhIHN0cmFpZ2h0IGxpbmUgcmFuZ2luZyBmcm9tICgwOyAwKSB0byAoTDsgMCkuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygc3RhbmRhcmQgb3V0cHV0IHNob3VsZCBjb250YWluIGEgc2luZ2xlIG51bWJlciAtIHRoZSBtYXhpbWFsIGRpc3RhbmNlIG9mIGEgcG9pbnQgb24gdGhlIGhpZ2h3YXkgdG8gdGhlIG5lYXJlc3QgYmFzZSB0cmFuc2NlaXZlciBzdGF0aW9uLiBZb3VyIG91dHB1dCB3aWxsIGJlIHJlZ2FyZGVkIGFzIGNvcnJlY3QgaWYgaXQgZGlmZmVycyBieSBhdCBtb3N0IDEwPHN1cD4tMzxcL3N1cD4gZnJvbSB0aGUgcHJlY2lzZSByZXN1bHQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2012 2번