ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

USU Junior Contest October'2005

About     Problems     Submit solution     Judge status     Standings
Contest is over

F. Goat in the Garden 5

Time limit: 1.0 second
Memory limit: 64 MB
Petr Vasilyevich is in a rage! His neighbor Vasiliy Petrovich grazed his goat in Petr Vasilyevich’s garden! Vasiliy Petrovich was not very long-sighted: Petr Vasilyevich had two goats and both of them would eat up and trample down the neighbor’s garden now.
Vasiliy Petrovich’s garden is rather big and it is not paled. The goats would have to spend much time to fulfill the plan. But there are several trees in the garden. Therefore Petr Vasilyevich decided to fasten the goats to some trees and to let them graze. But he has to fasten a goat to a tree with the rope so that the animal would not reach another tree, otherwise the goat would get entangled in the rope. At the same time the goats should not reach each other, otherwise they would trample down the same territory.
In order to cause the maximal damage to his neighbor Petr Vasilyevich wants the total area that the goats could reach to be the maximal. But he couldn’t fasten the goat closer than 1 meter and further than 50 meters from a tree.


The first line contains integer N (2 <= N <= 1000) – the number of trees in the garden. The next N lines contain the trees coordinates. The origin of coordinates is in the center of the garden. The coordinates are measured in meters with a one centimeter precision. The absolute values of the trees coordinates don’t exceed 100 meters. You may assume that the goat is fastened so that it can’t leave the plot’s area. A size of a goat can be neglected. It’s guaranteed that the goats can be fastened in the way described above.


Print the maximal area that Petr Vasilyevich’s goats would be able to trample down. Area must be printed in square meters (m2) with a precision of 1 square centimeter (cm2).


1 1
-2 0
5 3
-2 3
8 3.10
-2 -1
-2 2
8 4.10
Problem Author: Vladimir Yakovlev
Problem Source: The 12th High School Pupils Collegiate Programming Contest of the Sverdlovsk Region (October 15, 2005)
To submit the solution for this problem go to the Problem set: 1405. Goat in the Garden 5