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

Autumn school contest 2008

About     Problems     Submit solution     Judge status     Standings
Contest is over

B. Circle of Winter

Time limit: 1.0 second
Memory limit: 64 MB
Lich Sandro declared war to the King of Hell, and now hordes of demons are fighting fiercely against Sandro's army of the undead. Sandro has mastered the Magic of Fire, but the creatures of Hell can't be damaged by fire. That's why Sandro decided to use a “Circle of Winter” spell against them. This spell creates an indestructable circular-shaped ice wall. The demons who are touched by the circumference die immediately; the demons enclosed in a circle stay alive, but can't participate in the fight anymore.
Sandro can teleport to any point of the battlefield instantly and cast a “Circle of Winter” there. An ice wall centered in that point will appear in that case. Note that Sandro's magic skills allow him to cast a wall with a radius not exceeding 10000 metres. Now Sandro wants to choose a point to teleport to and a radius of a spell in such way that at least one demon would be killed and all the rest would be enclosed in a circle.


The first line contains an integer n — the number of demons (1 ≤ n ≤ 100). Demons can be considered as points on the battlefield. The next n lines contain n pairs of space-separated integers (x, y) — the coordinates of the demons relative to the point Sandro occupies before teleportation. Coordinates are given in metres and don't exceed 1000 in absolute value. Each point of the battlefield contains no more than one demon; also a demon can't occupy a point the Sandro occupies before teleportation.


Output 3 real numbers precise up to 10−9 — the coordinates of a point Sandro should teleport to and the radius of a “Circle of Winter” he should create. Sandro can't teleport to a point that is occupied by a demon. It is guaranteed that the solution always exists.


1 1
1 5
3 6
5 3
8 0
9 5
5 9
5 4 5
0 2
2 0
1 1 1.41421356237309
Problem Author: Dmitry Ivankov (prepared by Alexander Ipatov)
Problem Source: USU Junior Contest, October 2008
To submit the solution for this problem go to the Problem set: 1640. Circle of Winter