시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 151 27 22 19.298%

문제

누구나 다 아는 꿍텔레콤은 새로 건설된 고속도로에 꿍전파를 널리 퍼뜨리기 위해 여러 기지국들을 세우려고 했다. 하지만 언제나 어설픈 꿍은 발전소가 없다는 것을 뒤늦게 알아차렸다. 기지국마다 발전소를 만들 수는 없으므로 단 하나의 발전소만을 만들어 기지국들에 전력을 공급해야 한다. 이때 발전소는 고속도로상에 지을 예정이며 고속도로상의 임의의 지점에서 가장 가까운 기지국까지의 거리를 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+XHViMmU0XHVjNzRjIE5cdWM5MDRcdWM3NDAgeGksIHlpICgtMTBeOSAmbGU7IHhpLCB5aSAmbGU7MTBeOSkgXHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljMFx1YjI5NFx1YjM3MCBcdWFjMDFcdWFjMDEgXHVhZTMwXHVjOWMwXHVhZDZkXHVjNzU4IHgsIHlcdWM4OGNcdWQ0NWNcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViYTcwIFx1YmFhOFx1YjRlMCBcdWM4MTBcdWI0ZTRcdWM3NDAgXHVjOTExXHViY2Y1XHViNDE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHVjODhjXHVkNDVjXHViNGU0XHVjNzQwIHhcdWM4OGNcdWQ0NWNcdWFjMTJcdWM3NDQgXHVhZTMwXHVjOTAwXHVjNzNjXHViODVjIFx1YzYyNFx1Yjk4NFx1Y2MyOFx1YzIxY1x1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAgXHVhYzE5XHVjNzQwIHhcdWM4OGNcdWQ0NWNcdWFjMTJcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjXHViMjk0IHlcdWM4OGNcdWQ0NWNcdWFjMTJcdWM3NDQgXHVhZTMwXHVjOTAwXHVjNzNjXHViODVjIFx1YzYyNFx1Yjk4NFx1Y2MyOFx1YzIxY1x1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWNlMFx1YzE4ZFx1YjNjNFx1Yjg1Y1x1YjI5NCAoMCwwKSBcdWJkODBcdWQxMzAgKEwsMClcdWFlNGNcdWM5YzBcdWM3NTggXHVjNzdjXHVjOWMxXHVjMTIwIFx1YjNjNFx1Yjg1Y1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5kXHVhYzEyXHViNGU0IFx1YzkxMSBcdWNkNWNcdWIzMDBcdWFjMDAgXHViNDE4XHViMjk0IFx1YWMxMiBcdWIyZTggXHVkNTU4XHViMDk4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlOCwgXHVjMThjXHVjMjE4XHVjODEwIFx1YzU0NFx1Yjc5OCAzXHVjNzkwXHViOWFjXHVhZTRjXHVjOWMwXHVjNzU4IFx1YzgxNVx1ZDY1NVx1YjNjNFx1Yjk3YyBcdWFjMDBcdWM4MzhcdWM1N2NcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMzQ2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTW9iaWxlIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgd2VsbC1rbm93biBtb2JpbGUgbmV0d29yayBvcGVyYXRvciBUb3RhbHBob25lIGhhcyBzZXQgdXAgYSBudW1iZXIgb2YgbmV3IGJhc2UgdHJhbnNjZWl2ZXIgc3RhdGlvbnMgaW4gb3JkZXIgdG8gY292ZXIgYSBuZXdseS1idWlsdCBoaWdod2F5IHdpdGggaXRzIG5ldHdvcmsuIEFzIGFsd2F5cyB0aGUgcHJvZ3JhbW1lcnMgb2YgVG90YWxwaG9uZSBoYXZlIGJlZW4gc2xvcHB5OyBhcyBhIHJlc3VsdCwgdGhlIHRyYW5zbWlzc2lvbiBwb3dlciBjYW5ub3QgYmUgc2V0IHVwIGluZGl2aWR1YWxseSBmb3IgdGhlIHN0YXRpb25zLCBidXQgb25lIGNhbiBvbmx5IHNldCB0aGUgdHJhbnNtaXNzaW9uIHBvd2VyIHRvIGEgZml4ZWQgY29tbW9uIHZhbHVlIGZvciBhbGwgdGhlIHN0YXRpb25zLiBJbiBvcmRlciB0byBtaW5pbWl6ZSBwb3dlciBjb25zdW1wdGlvbiwgdGhlIGNvbXBhbnkgd2FudHMgdG8ga25vdyB0aGUgbWF4aW1hbCBkaXN0YW5jZSBvZiBhIHBvaW50IG9uIHRoZSBoaWdod2F5IHRvIHRoZSBuZWFyZXN0IGJhc2UgdHJhbnNjZWl2ZXIgc3RhdGlvbi48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnNpc3RzIG9mIHR3byBpbnRlZ2VycyBOKDEgJmxlOyBOICZsZTsgMTA8c3VwPjY8XC9zdXA+KSBhbmQgTCgxICZsZTsgTCAmbGU7IDEwPHN1cD45PFwvc3VwPikgcmVwcmVzZW50aW5nIHRoZSBudW1iZXIgb2YgYmFzZSB0cmFuc2NlaXZlciBzdGF0aW9ucyBhbmQgdGhlIGxlbmd0aCBvZiB0aGUgaGlnaHdheSwgcmVzcGVjdGl2ZWx5LiBOIGxpbmVzIGZvbGxvdywgZWFjaCBjb250YWluaW5nIGEgcGFpciBvZiBpbnRlZ2VycyB4PHN1Yj5pPFwvc3ViPiwgeTxzdWI+aTxcL3N1Yj4gKC0xMDxzdXA+OTxcL3N1cD4gJmxlOyB4PHN1Yj5pPFwvc3ViPiwgeTxzdWI+aTxcL3N1Yj4gJmxlOzEwPHN1cD45PFwvc3VwPikgd2hpY2ggZGVzY3JpYmVzIHRoZSBjb29yZGluYXRlcyBvZiBhIGJhc2UgdHJhbnNjZWl2ZXIgc3RhdGlvbi4gQWxsIHBvaW50cyBhcmUgZGlzdGluY3QuIENvb3JkaW5hdGVzIGFyZSBzb3J0ZWQgaW4gdGhlIG5vbi1kZWNyZWFzaW5nIG9yZGVyIHdpdGggcmVzcGVjdCB0byB4PHN1Yj5pPFwvc3ViPiBjb29yZGluYXRlcy4gSWYgdHdvIHZhbHVlcyBvZiB4PHN1Yj5pPFwvc3ViPiBhcmUgdGhlIHNhbWUsIHRoZW4gY29vcmRpbmF0ZXMgYXJlIHNvcnRlZCB3aXRoIHJlc3BlY3QgdG8geTxzdWI+aTxcL3N1Yj4gY29vcmRpbmF0ZXMgaW4gaW5jcmVhc2luZyBvcmRlci48XC9wPlxyXG5cclxuPHA+VGhlIGhpZ2h3YXkgaXMgYSBzdHJhaWdodCBsaW5lIHJhbmdpbmcgZnJvbSAoMDsgMCkgdG8gKEw7IDApLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIHN0YW5kYXJkIG91dHB1dCBzaG91bGQgY29udGFpbiBhIHNpbmdsZSBudW1iZXIgLSB0aGUgbWF4aW1hbCBkaXN0YW5jZSBvZiBhIHBvaW50IG9uIHRoZSBoaWdod2F5IHRvIHRoZSBuZWFyZXN0IGJhc2UgdHJhbnNjZWl2ZXIgc3RhdGlvbi4gWW91ciBvdXRwdXQgd2lsbCBiZSByZWdhcmRlZCBhcyBjb3JyZWN0IGlmIGl0IGRpZmZlcnMgYnkgYXQgbW9zdCAxMDxzdXA+LTM8XC9zdXA+IGZyb20gdGhlIHByZWNpc2UgcmVzdWx0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2012 2번

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