Power Plant on the Highway
Time limit1sMemory limit128 MB
Given base stations anywhere in the plane, find the point on a fixed highway segment that maximizes the minimum distance to any station, and output the squared distance as an exact reduced fraction.
- Level
Medium7 of 10
- Topics
- Binary search, Geometry, Math
- Solved
- No attempts yet
Problem
A telecom company has installed several base stations along a newly built highway. To supply power to these base stations, the company will build exactly one power plant somewhere on the highway.
The highway is the segment from point to point in the coordinate plane. The power plant may be placed at any point on this segment.
For a point on the highway, let be the distance from that point to its nearest base station. Among all points where the power plant could be placed, the company wants to choose the one that maximizes . Find this maximum possible value of .
Input
The first line contains two integers () and (), separated by a space, where is the number of base stations and is the length of the highway.
Each of the next lines contains the coordinates , () of a base station. All base station coordinates are distinct. The coordinates are given in increasing order of ; ties in are broken by increasing .
The highway is the straight segment from to , while base stations may lie anywhere in the plane.
Output
The maximum value is always the square root of a rational number, so instead of itself, output as an irreducible fraction.
Writing with and , print it on a single line in the form p/q. Always use the p/q form, even when the denominator equals (for example, 25/1).