本站作为LDUOnlineJudge的测试版本进行演示,官方网站请访问http://icpc.ldu.edu.cn

1351. Build the Perfect House


Description

Alice and Bob are now 45 years old and have enjoyed a long  ve-years retirement maintaining their vegetable  field. Going back and forth to the  eld from their house in the city has become a really exhausting task, so they decided to move to the  eld 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  eld 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  nd the maximum perimeter a perfect house can have.

Input

The first line contains an integer \$N (1 \leq N \leq 10^4)\$ indicating the number of vegetable plants in Alice and Bob's  eld. 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 vegetable plant with two integers \$X\$ and \$Y\$ (\$-10^9 \leq X, Y \leq 10^9\$) indicatinggthe coordinates of the plant. No two vegetable plants have the same location and none of them is at point \$(0, 0)\$.

Output

Output a single line with a number indicating the maximum perimeter a perfect house can have. The result must be output as a rational number with exactly four digits after the decimal point, rounded if necessary. Notice that the sides of the house don't need to be aligned with the coordinate axes.

Samples

Input Copy
1
0 1
Output
8.0000
Input Copy
2
10 4
-5 -8
Output
74.9634

Source

ICPC Latin American Regional 2019
Problem Information

Time Limit: 2000MS (C/C++,Others×2)
Memory Limit: 256MB (C/C++,Others×2)
Special Judge: No
AC/Submit: 1 / 1
Tags:
Contests involved

1039. ICPC Latin American Regional 2019
My history solutions

You didn't submit any solution!
Submit your solution

Login Register