Czech ACM Student Chapter

Czech Technical University in Prague

Charles University in Prague

Technical University of Ostrava

ˇ a

Slovak University of Technology

Pavol Jozef Saf´rik University in Koˇice

s

ˇ

University of Zilina

Masaryk University

Matej Bel University in Bansk´ Bystrica

a

University of West Bohemia

CTU Open Contest 2013

Fence Orthogonality

fo.c, fo.cpp, Fo.java

Evil bunnies are eating Freddy's vegetables. In order to stop them, he decided to build a fence

enclosing all vegetables in his garden. Freddy wants the fence to be as cheap (i.e., short) as

possible, but for technical reasons, he can only build rectangular fences. For simplicity, we will

assume the vegetables are negligibly small and can be represented by points in a two-dimensional

plane.

Input Specification

The input consists of several test cases. The first line of each test case contains one integer N

(3 ≤ N ≤ 10 000) giving the number of vegetables in the garden. Each of the following N lines

contains two integers Xi and Yi (0 ≤ Xi, Yi ≤ 10 000), giving the coordinates of one vegetable to

be protected. No two vegetables have the same coordinates. You may also assume the vegetables

are not all on the same straight line.

Output Specification

For each test case, output a single line containing one real number t, giving the smallest length

of the perimeter of a rectangular fence enclosing all the vegetables. Note that the edges of the

rectangle do not need to be parallel with the coordinate axes.

The answer will be accepted as correct if the difference between t and the exact answer is at

most 0.0005.

Sample Input

Output for Sample Input

3

4

00

31.112698

10

5.656854

01

3

10 0

0 10

44

4

10

01

21

12