시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 120 22 17 19.767%

문제

누구나 다 아는 꿍텔레콤은 새로 건설된 고속도로에 꿍전파를 널리 퍼뜨리기 위해 여러 기지국들을 세우려고 했다. 하지만 언제나 어설픈 꿍은 발전소가 없다는 것을 뒤늦게 알아차렸다. 기지국마다 발전소를 만들수는 없으므로 단 하나의 발전소만을 만들어 기지국들에 전력을 공급해야 한다. 이때 발전소는 고속도로상에 지을 예정이며 고속도로상의 임의의 지점에서 가장 가까운 발전소까지의 거리를 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+XHJcblxyXG48cD5cdWQ1NThcdWM5YzBcdWI5Y2MgXHVhZmNkXHVjNzQwIFx1YzViOFx1YzgxY1x1YjA5OCBcdWM1YjRcdWMxMjRcdWQ1MDRcdWIyZTQuIFx1Yzc3NFx1YmM4OFx1YzVkMFx1YjNjNCBcdWM1ZWNcdWI3ZWNcdWJkODRcdWM3NTggXHViM2M0XHVjNmMwXHVjNzc0IFx1ZDU0NFx1YzY5NFx1ZDU1OFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1Yzc0MCBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCBOKDEgJmxlOyBOICZsZTsgMTBeNikgYW5kIEwoMSAmbGU7IEwgJmxlOyAxMF45KVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAgTlx1Yzc0MCBcdWFlMzBcdWM5YzBcdWFkNmRcdWM3NTggXHVhYzFjXHVjMjE4LCBMXHVjNzQwIFx1YWNlMFx1YzE4ZFx1YjNjNFx1Yjg1Y1x1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTlx1YzkwNFx1Yzc0MCB4aSwgeWkgKC0xMF45ICZsZTsgeGksIHlpICZsZTsxMF45KSBcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWMwXHViMjk0XHViMzcwIFx1YWMwMVx1YWMwMSBcdWFlMzBcdWM5YzBcdWFkNmRcdWM3NTggeCwgeVx1Yzg4Y1x1ZDQ1Y1x1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWJhNzAgXHViYWE4XHViNGUwIFx1YzgxMFx1YjRlNFx1Yzc0MCBcdWM5MTFcdWJjZjVcdWI0MThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiBcdWM4OGNcdWQ0NWNcdWI0ZTRcdWM3NDAgeFx1Yzg4Y1x1ZDQ1Y1x1YWMxMlx1Yzc0NCBcdWFlMzBcdWM5MDBcdWM3M2NcdWI4NWMgXHVjNjI0XHViOTg0XHVjYzI4XHVjMjFjXHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCBcdWFjMTlcdWM3NDAgeFx1Yzg4Y1x1ZDQ1Y1x1YWMxMlx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWNcdWIyOTQgeVx1Yzg4Y1x1ZDQ1Y1x1YWMxMlx1Yzc0NCBcdWFlMzBcdWM5MDBcdWM3M2NcdWI4NWMgXHVjNjI0XHViOTg0XHVjYzI4XHVjMjFjXHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhY2UwXHVjMThkXHViM2M0XHViODVjXHViMjk0ICgwLDApIFx1YmQ4MFx1ZDEzMCAoTCwwKVx1YWU0Y1x1YzljMFx1Yzc1OCBcdWM3N2NcdWM5YzFcdWMxMjAgXHViM2M0XHViODVjXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPmRcdWFjMTJcdWI0ZTQgXHVjOTExIFx1Y2Q1Y1x1YjMwMFx1YWMwMCBcdWI0MThcdWIyOTQgXHVhYzEyIFx1YjJlOCBcdWQ1NThcdWIwOThcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU4LCBcdWMxOGNcdWMyMThcdWM4MTAgXHVjNTQ0XHViNzk4IDNcdWM3OTBcdWI5YWNcdWFlNGNcdWM5YzBcdWM3NTggXHVjODE1XHVkNjU1XHViM2M0XHViOTdjIFx1YWMwMFx1YzgzOFx1YzU3Y1x1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMzQ2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTW9iaWxlIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgd2VsbC1rbm93biBtb2JpbGUgbmV0d29yayBvcGVyYXRvciBUb3RhbHBob25lIGhhcyBzZXQgdXAgYSBudW1iZXIgb2YgbmV3IGJhc2UgdHJhbnNjZWl2ZXIgc3RhdGlvbnMgaW4gb3JkZXIgdG8gY292ZXIgYSBuZXdseS1idWlsdCBoaWdod2F5IHdpdGggaXRzIG5ldHdvcmsuIEFzIGFsd2F5cyB0aGUgcHJvZ3JhbW1lcnMgb2YgVG90YWxwaG9uZSBoYXZlIGJlZW4gc2xvcHB5OyBhcyBhIHJlc3VsdCwgdGhlIHRyYW5zbWlzc2lvbiBwb3dlciBjYW5ub3QgYmUgc2V0IHVwIGluZGl2aWR1YWxseSBmb3IgdGhlIHN0YXRpb25zLCBidXQgb25lIGNhbiBvbmx5IHNldCB0aGUgdHJhbnNtaXNzaW9uIHBvd2VyIHRvIGEgZml4ZWQgY29tbW9uIHZhbHVlIGZvciBhbGwgdGhlIHN0YXRpb25zLiBJbiBvcmRlciB0byBtaW5pbWl6ZSBwb3dlciBjb25zdW1wdGlvbiwgdGhlIGNvbXBhbnkgd2FudHMgdG8ga25vdyB0aGUgbWF4aW1hbCBkaXN0YW5jZSBvZiBhIHBvaW50IG9uIHRoZSBoaWdod2F5IHRvIHRoZSBuZWFyZXN0IGJhc2UgdHJhbnNjZWl2ZXIgc3RhdGlvbi48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIHRleHQgZmlsZSBtb2JpbGUuaW4gY29uc2lzdHMgb2YgdHdvIGludGVnZXJzIE4oMSAmbGU7IE4gJmxlOyAxMDxzdXA+NjxcL3N1cD4pIGFuZCBMKDEgJmxlOyBMICZsZTsgMTA8c3VwPjk8XC9zdXA+KSByZXByZXNlbnRpbmcgdGhlIG51bWJlciBvZiBiYXNlIHRyYW5zY2VpdmVyIHN0YXRpb25zIGFuZCB0aGUgbGVuZ3RoIG9mIHRoZSBoaWdod2F5LCByZXNwZWN0aXZlbHkuIE4gbGluZXMgZm9sbG93LCBlYWNoIGNvbnRhaW5pbmcgYSBwYWlyIG9mIGludGVnZXJzIHg8c3ViPmk8XC9zdWI+LCB5PHN1Yj5pPFwvc3ViPiAoLTEwPHN1cD45PFwvc3VwPiAmbGU7IHg8c3ViPmk8XC9zdWI+LCB5PHN1Yj5pPFwvc3ViPiAmbGU7MTA8c3VwPjk8XC9zdXA+KSB3aGljaCBkZXNjcmliZXMgdGhlIGNvb3JkaW5hdGVzIG9mIGEgYmFzZSB0cmFuc2NlaXZlciBzdGF0aW9uLiBBbGwgcG9pbnRzIGFyZSBkaXN0aW5jdC4gQ29vcmRpbmF0ZXMgYXJlIHNvcnRlZCBpbiB0aGUgbm9uLWRlY3JlYXNpbmcgb3JkZXIgd2l0aCByZXNwZWN0IHRvIHg8c3ViPmk8XC9zdWI+IGNvb3JkaW5hdGVzLiBJZiB0d28gdmFsdWVzIG9mIHg8c3ViPmk8XC9zdWI+IGFyZSB0aGUgc2FtZSwgdGhlbiBjb29yZGluYXRlcyBhcmUgc29ydGVkIHdpdGggcmVzcGVjdCB0byB5PHN1Yj5pPFwvc3ViPiBjb29yZGluYXRlcyBpbiBpbmNyZWFzaW5nIG9yZGVyLjxcL3A+XHJcblxyXG48cD5UaGUgaGlnaHdheSBpcyBhIHN0cmFpZ2h0IGxpbmUgcmFuZ2luZyBmcm9tICgwOyAwKSB0byAoTDsgMCkuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2YgdGhlIHRleHQgZmlsZSBtb2JpbGUub3V0IHNob3VsZCBjb250YWluIGEgc2luZ2xlIG51bWJlciAtIHRoZSBtYXhpbWFsIGRpc3RhbmNlIG9mIGEgcG9pbnQgb24gdGhlIGhpZ2h3YXkgdG8gdGhlIG5lYXJlc3QgYmFzZSB0cmFuc2NlaXZlciBzdGF0aW9uLiBZb3VyIG91dHB1dCB3aWxsIGJlIHJlZ2FyZGVkIGFzIGNvcnJlY3QgaWYgaXQgZGlmZmVycyBieSBhdCBtb3N0IDEwPHN1cD4tMzxcL3N1cD4gZnJvbSB0aGUgcHJlY2lzZSByZXN1bHQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2012 2번