Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana
Alice and Bob are now $45$ years old and have enjoyed a long five-years retirement maintaining their vegetable field. Going back and forth to the field from their house in the city has become a really exhausting task, 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? Well, you know, there are some requirements. The area of the house must be a square centered at the point of the field that has the most beautiful view. Besides, the house cannot be built over any of the vegetables, although 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 \le N \le 10^4$) indicating the number of vegetable plants in Alice and Bob's field. Vegetable plants are represented as points in the two-dimensional plane, being $(0,0)$ the point of the field that has the most beautiful view. Each of the next $N$ lines describes a % different vegetable plant with two integers $X$ and $Y$ ($-10^9 \le X, Y \le 10^9$) indicating the coordinates of the plant.
No two vegetable plants have the same location and none of them is at point $(0,0)$.
Output
A number indicating the maximum perimeter a perfect house can have. Notice that the sides of the house don't need to be aligned with the coordinate axes.