Map Labels
Time limit2sMemory limit128 MB
Given city points, find the maximum label height so that fixed-ratio (3:1) rectangles anchored at each point never overlap, using binary search on the height with an efficient feasibility check.
- Level
Medium6 of 10
- Topics
- Binary search, Sorting, Geometry
- Solved
- No attempts yet
Problem
You want to place city names on a map without overlaps.
The position of each city is given as an (x, y) coordinate. Every city name is written inside an axis-aligned rectangle of the same size, and each rectangle's width is three times its height. For a city, the rectangle is placed to the lower right of the city coordinate, using the city coordinate as its upper-left corner. For instance, if the city is at (5, 3) and the rectangle has width 3 and height 1, the rectangle occupies the region from (5, 3) to (8, 2).
Two rectangles may share points or line segments on their boundaries. They must not overlap in any region with positive area.
Find the maximum possible height of the rectangles so that every city can be labeled. The width of each rectangle is always three times that value.
Input
The first line contains the number of cities n. (2 ≤ n ≤ 100,000)
Each of the next n lines contains two nonnegative integers x and y, the coordinates of one city. (0 ≤ x, y ≤ 1,000,000)
No two cities are given with the same coordinates.
Output
Print the maximum possible rectangle height on the first line.
Round the answer to the second digit after the decimal point, and always print exactly two digits after the decimal point.