Czech ACM Student Chapter
Czech Technical University in Prague
Charles University in Prague
Technical University of Ostrava
acm
ˇ a
Slovak University of Technology
Pavol Jozef Saf´rik University in Koˇice
s
cz
ˇ
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
