REDCROSS - Red Cross Hospital

no tags 

The Red Cross is a humanitarian and neutral organization that strives to provide assistance to victims of civil wars and other situations of serious violence.

Recently, Nlogônia entered into a political crisis that culminated in a great civil war. This war wrecked Dozens of innocent communities across the country. Seeing the calamity situation in which the country joined, the Red Cross decided to help the population in all affected regions in Nlogônia.

For this, it was decided that a hospital base will be installed to support the Red Cross in the country. However, the summit do not know where to build the base of Red Cross hospital. You and your team were hired to tell the Red Cross the position that they must build the hospital, with the constraint that the distance to the farthest community from the hospital is as small as possible.

Input

The input file consists of several test cases. For each test case, the first line contains the number of affected communities N to be served. Each of the following N lines contains a localization of each community. Localization is represented by decimal coordinates X and Y. After the first test case will be another line with a new test case defined by number of communities N. The input never contains repeated coordinates for each community in each test case and the input ends with N=0.

Suppose:
0<=N<=100000
(-100000,-100000)<=X,Y<=(100000, 100000)

Output

For each test case of your program prints just a one line with two decimal number separated by
commas indicating the optimum location for the construction of the base hospital, regardless of the
area have a built space. Each coordinate must be printed with four decimal place of accuracy.

Example

Input:
2
-1 0
1 0
4
0.5  0.5
0.5 -0.5
0.0  0.5
0.0 -0.5
0
Output:
0.0000, 0.0000
0.2500, 0.0000

Added by:Diogo Soares [UFAM]
Date:2012-06-11
Time limit:0.111s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel Pentium G860 3GHz)
Languages:All
Resource:Own Problem

hide comments
[deleted]: 2012-06-19 17:21:12

I 'm getting WA again and again.. What could be possible reason? logic is correct and sample input is giving correct output.. plz clarify about the space/comma thing

Diogo Soares [UFAM]: 2012-06-19 17:21:12

yes! There is a space after comma

Abhishek Sanghai: 2012-06-19 17:21:12

is there a space after , in output?

Pranay: 2012-08-29 18:46:39

Last edit: 2012-06-11 18:14:53
Nnavneetsinha: 2012-08-29 18:46:33

Last edit: 2012-06-12 05:30:42