Building the Perfect House
Time limit1.5sMemory limit512 MB
Given N points, none at the origin, find the largest square centered at the origin that contains no point strictly inside it, then print its perimeter to four decimals.
- Level
Hard8 of 10
- Topics
- Geometry, Binary search, Math, Sorting
- Solved
- No attempts yet
Problem
Alice and Bob are now 45 years old and have spent a long five-year retirement tending their vegetable field. Traveling back and forth between their house in the city and the field has become exhausting, so they decided to move to the field permanently. They currently have a perfect fence surrounding all the vegetable plants (it has minimum perimeter and area), but they will tear down the old fence and build a new perfect house to live in.
So what is a perfect house? There are some requirements. The area of the house must be a square centered at the point of the field with the most beautiful view. Also, the house cannot be built over any of the vegetables, though vegetables are allowed right on the border of the house.
Since Alice and Bob love spacious rooms, your task is to find the maximum perimeter a perfect house can have.
Input
The first line contains an integer N (1 ≤ N ≤ 104), the number of vegetable plants in Alice and Bob's field. Vegetable plants are points in the two-dimensional plane, and (0, 0) is the point of the field with the most beautiful view. Each of the next N lines describes a vegetable plant with two integers X and Y (−109 ≤ X, Y ≤ 109), the coordinates of the plant. No two vegetable plants have the same location, and none of them is at (0, 0).
Output
Output a single line with a number, the maximum perimeter a perfect house can have. The result must be printed as a rational number with exactly four digits after the decimal point, rounded if necessary. Note that the sides of the house do not need to be aligned with the coordinate axes.