Under construction

Still being built. Things may change

Power Plant on the Highway

Time limit1sMemory limit128 MB

Summary
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 (0,0)(0, 0) to point (L,0)(L, 0) in the coordinate plane. The power plant may be placed at any point on this segment.

For a point on the highway, let dd 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 dd. Find this maximum possible value of dd.

Input

The first line contains two integers NN (1≤N≤1061 \le N \le 10^6) and LL (1≤L≤1091 \le L \le 10^9), separated by a space, where NN is the number of base stations and LL is the length of the highway.

Each of the next NN lines contains the coordinates xix_i, yiy_i (−109≤xi,yi≤109-10^9 \le x_i, y_i \le 10^9) of a base station. All base station coordinates are distinct. The coordinates are given in increasing order of xx; ties in xx are broken by increasing yy.

The highway is the straight segment from (0,0)(0, 0) to (L,0)(L, 0), while base stations may lie anywhere in the plane.

Output

The maximum value dd is always the square root of a rational number, so instead of dd itself, output d2d^2 as an irreducible fraction.

Writing d2=pqd^2 = \dfrac{p}{q} with q≥1q \ge 1 and gcd⁡(p,q)=1\gcd(p, q) = 1, print it on a single line in the form p/q. Always use the p/q form, even when the denominator qq equals 11 (for example, 25/1).

Examples3

  1. Example 1

    Input
    2 10
    0 0
    11 1
    
    Expected output
    3721/121
    
  2. Example 2

    Input
    2 10
    0 0
    10 0
    
    Expected output
    25/1
    
  3. Example 3

    Input
    2 7
    0 0
    7 0
    
    Expected output
    49/4