시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
4 초 | 128 MB | 7 | 1 | 1 | 50.000% |
One of the biggest problems in modern cartography is writing geographic names on the map. If you write on a map the name of each city, town and a village, then some of the names will overlap and the map will become unreadable.
You are given a coordinates of all the points in a Cartesian plane, which are to be marked. The area in which you should write the name is the rectangle which has sides paralel to the axes, and the width is exactly three times the height.
For each point there has to be exactly one rectangle, so that the point which it marks is in his top left corner (i.e. the area for the name has to be bottom-right from the point). Areas for all names must have same dimensions.
Write a program which will find the maximum size of the area for the name, after every point is marked and no two areas for the names overlap (they can touch by an edge or a vertex).
All the coordinates of the given points will be positive integers less than or equal to 1,000,000 (one million). It is allowed for parts of rectangles to leave that area (i.e. some parts of rectangles might exceed the given limit).
In the first line, there will be an integer N (number of points on the map), 2 ≤ N ≤ 100,000.
In the next N lines there will be two integers X and Y, 0 ≤ X, Y ≤ 1,000,000, coordinates of points. No two points will have the same coordinates.
In the first and only line of output you should write the height of rectangle, real decimal number rounded to two decimal places.
Your output value must be within 0.01 absolute error of the correct value.
3 0 0 5 4 3 7
3.00
5 1 1 6 5 18 3 9 9 16 15
4.00
10 26 77 12 37 14 18 19 96 71 95 91 9 98 43 66 77 2 75 94 91
7.67