ALIENS - Aliens

no tags 

Aliens visited our planet with an obvious intention to find some new species for their space zoo. After entering Earth's orbit, they positioned themselves over the town of Belgrade, having detected some life-form activity on the ground. As they approached the surface, they saw a group of half-intelligent beings. Those creatures were actually competitors of the Balkan Olympiad in Informatics who were enjoying the excursion after intense contest. Aliens want to abduct all n (2<=n<=100000) competitors since they are very compassionate, and don’t want their creatures to feel lonely in the space zoo.
Aliens use tractor beam to take their prey. Tractor beam works in the following way: it projects a circle-shaped beam from the spacecraft to the ground vertically beneath it, and all beings that are found in that circle or on its boundary are taken. Projecting the tractor beam needs a certain amount of energy to be spent. As the radius of the tractor beam (radius of the circle on the ground) increases, more and more energy is required. Although extremely intelligent, aliens are much more advanced in social sciences than in programming. That’s why they are asking you to help them find the position of their spacecraft so that the energy required to take all of the n competitors is minimal.
Help our alien brothers! Write a program that will find the required minimal radius of tractor beam that contains all n competitors and the optimal spacecraft location - which is the same as the center of the circle on the ground.

Input

First line of input contains one integer c<=20 - number of test cases. Each test case begins with number n (2<=n<=100000). Then n lines follow and i-th of them contains two real numbers xi and yi (-10000.0<=xi,yi<=10000.0) representing coordinates of the i-th competitor.

Output

For each test case output radius of the tractor beam and coordinates of the spacecraft. Numbers should be rounded to two decimal places.

Example

Input:
1
6
8.0 9.0
4.0 7.5
1.0 2.0
5.1 8.7
9.0 2.0
4.5 1.0

Output:
5.00
5.00 5.00
Warning: large Input/Output data, be careful with certain languages

hide comments
alok_0366: 2019-06-13 11:32:48

Last edit: 2019-06-13 11:33:30
wiseh: 2018-05-09 15:24:47

Why time limit exceeded and no matter what I do?
On ideone program works correctly for 55-70 milliseconds.

Last edit: 2018-05-09 15:27:22
ales9914: 2017-05-31 05:59:01

Can I use the math library?

NIKHIL KUMAR SINGH: 2015-04-08 09:11:45

First allocated the memory of 3000002 for the array ,got segmentation fault ,....REDUCED it to 300002 got AC ...Don't know WTF is this

Amirmohsen: 2014-05-28 20:16:17

i am getting runtime error
i think it's because of stacks size limit
what is the stack size limit ?


Added by:gawry
Date:2004-07-21
Time limit:0.625s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Balkan Olympiad in Informatics 2002