Computer geeks! Show off your skills and claim the job of your dreams! RecruitCoders.com

SPOJ Problem Set (classical)

9459. Connecting three towns (variation)

Problem code: THREETW1

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

Added by:	HWK
Date:	2011-08-25
Time limit:	1s
Source limit:	50000B
Languages:	All

hide comments

2011-09-25 01:15:32 ZiYuan
Thank you, @HWK. I am done.

Last edit: 2011-09-25 03:16:06

2011-09-24 23:37:48 HWK
@ZiYuan:
E.g. 39 48 98 82 88 42

2011-09-24 18:34:50 ZiYuan
Weird. I've passed the challenge version, but failed in this one. @HWK, can you tell me the test case I didn't pass? Thank you. (5718652)

Last edit: 2011-09-24 18:35:33

2011-09-11 09:52:51 HWK
@Manish Jain: E.g. look at the 2nd example. Your answer there is '2 1' not '1 0'.

2011-09-10 22:23:33 Manish Jain
@HWK:-why i m getting WA??
i think i m using d correct algo.
would u pls point me where my code fails..?
my solution id:5637542

Last edit: 2011-09-10 23:18:53

2011-08-31 12:03:56 [Retired] Blue.Mary
The challenge version of this problem is here: http://www.spoj.pl/problems/THREETWN

2011-08-30 12:46:38 HWK
@Aurelian Tutuianu:
Another hint:
input - 46 61 5 97 68 69
your output - 46.0791736376 61.4109853749
my output - 46.0791729818 61.4109817954
This are no rounding problems.

2011-08-29 20:05:40 HWK
@Robin Lee: Thanks!

2011-08-29 14:59:01 Robin Lee
The rounding issue was clear from the problem statement and does not provide cause to attack the setter. Always print to 1dp more than requested if you have the opportunity.

Last edit: 2011-08-29 16:55:56

2011-08-29 13:36:49 HWK
@Damian Straszak: 0 0 1 0 5 0 -> 1 0
You're right: There's no intersection at this case.
I changed the problem description.
Thank You.
"%.6f" sometimes can be good enough, but sometimes because of rounding errors not. See my last comment and you propably will understand it.