SPOJ.com - Problem THREETW1

THREETW1 - Connecting three towns (variation)

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!

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

hide comments

2011-08-29 11:36:49 HWK
@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

2011-08-29 11:36:49 Aurelian Tutuianu
@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.

2011-08-29 11:36:49 Damian Straszak
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."?

2011-08-29 11:36:49 HWK
@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

2011-08-29 11:36:49 Pranay
@hwk: is the sum of the lenghts minimum or each individual length?
nice problem :)

Last edit: 2011-09-02 02:13:48

2011-08-29 11:36:49 HWK
@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