SPOJ.com - Problem THREETW1

THREETW1 - Connecting three towns (variation)

no tags

Given three towns find the point for which the summary distance to all towns is minimal. Wanted are the accurate coordinates ±10^-6.

Input

In the first line the number T (T<100) of test cases. Then T lines with the space separated coordinates (integer 0<=x, y<=100) of the three towns.

Output

For each test case the coordinates of the above specified point.

Example

Input:
2
2 2 1 1 2 1
1 0 0 0 2 1

Output:
1.788675 1.211324
1 0

Submit solution!

hide comments

< Previous 1 2 Next >

	HWK: 2011-08-29 11:36:49 @Aurelian Tutuianu: I use the standard SPOJ judge FP 10^-6. That's its comparing method: static bool equal (lexem a, lexem b) { if (a.type != b.type) return false; if (a.type==TP_EOF) return true; if (a.type==TP_CHAR) return (a.c==b.c); return (fabs(a.d-b.d)<=epsilon); } with double epsilon=0.000001; This method compares your output with my results which I've saved with 10 digits after the decimal point. Except for choosing the judge and preparing the test data I have no influence on the judging. I didn't find a better way to specify the 'rounding rules' of this judge than '+-10^-6'. That's one error in your output: input - 16 75 27 13 56 41 your output - 39.942763 39.811774 my ouput - 39.9427649493 39.8117728195 I hope this helps to solve your problem. Last edit: 2011-08-29 11:16:32
	Aurelian Tutuianu: 2011-08-29 11:36:49 @hwk: I consider that the problem should consist only in algorithm, not in a silly formatting thing. Especially when the formatting rules are not specified. I don't want to waste time to guess what rounding to apply. Perhaps you should better specify rounding rules in the problem statement. I renounced to solve it, even if I know the solution and the problem is nice.
	Damian Straszak: 2011-08-29 11:36:49 What is the answer for 0 0 1 0 5 0? There is no "intersection" in the optimal path network. You probably mean: find the point for which the summary distance to all three towns is minimal. And tell me please why: "'%.6f' isn't enough for AC."?
	HWK: 2011-08-29 11:36:49 @Pranay: Look at the last comment. You have to minimize the sum of the lengths. And keep in mind: '%.6f' isn't enough for AC. Hi, Aurelian Tutuianu! Look at your output! The precision isn't enough. ;-) Last edit: 2011-08-27 20:16:26
	Pranay: 2011-08-29 11:36:49 @hwk: is the sum of the lenghts minimum or each individual length? nice problem :) Last edit: 2011-09-02 02:13:48
	HWK: 2011-08-29 11:36:49 @Oleg: Why have you removed your question and my answer? Here's a recapitulation of the two deleted comments: 1. You have to minimize the summary length of all streets. 2. '%.6f' isn't enough for AC. Last edit: 2011-08-27 08:09:24

Submit solution!

Added by:	HWK
Date:	2011-08-25
Time limit:	0.100s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64