THREETWN - Connecting three towns

no tags 

Given three towns find the point for which the summary distance to all towns is as small as possible.

The shorter all streets together, the shorter your source code and the faster your code the better will be your score. For the street length you can get at most 10000000 points, for each of the other parts 5000. Thus the best score is 10010000.

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.78867513459 1.21132486541
1 0

hide comments
Mitch Schwartz: 2015-01-06 20:47:16

The nature of this problem may change quite a bit after cluster change.

Mitch Schwartz: 2012-10-03 18:41:09

@HWK: I finally isolated a strange thing with judging: the submission is regarded as WA if there's no whitespace at the very end of the output. Could this be changed? It prevents a certain improvement [edit: the improvement is now only 1 byte] I wanted to make. Such a change to the judge wouldn't affect the results for any previously AC solutions, so I think it would be ok. (No need to rejudge or disqualify anything.)

By the way very interesting challenge and score assessment, I just wish the server were a little faster, by a factor of maybe ~1.4 :p.

Last edit: 2012-10-03 19:24:48
Sourabh Singh: 2012-01-18 14:16:42

@HWK can u hint !! any tricky cases. m getting about 9881000 right..
ID 6367544

HWK: 2011-10-01 10:08:45

@The Raven: You can simply save at least 4 bytes.

HWK: 2011-09-02 11:39:16

@[Trichromatic] XilinX: Thanks! You gave the right answer.

XeRoN!X: 2011-09-02 08:42:14

@Xilinx, my bad, i ignored 0.01s runtime.
Thanks for replying.

[Rampage] Blue.Mary: 2011-09-02 01:46:40

(1) If you've printed all the correct answers, then your score equals to 10010000 - 5000 * (evaluation time) - (source code length).

(2) SPOJ machine is not that stable. If your solution's running time is judged as 0.01s, just re-submit. (I think this is not HWK's fault.)

XeRoN!X: 2011-09-01 22:24:48

@HWK, can you please tell me the size of Xilinx's solution.

Also, i think judge doesn't always evaluate correctly. e.g see my solution id -> 5593419. Its same as id -> 5593488. But score is different.

What's the condition for getting perfect score(10010000)?

Last edit: 2011-09-01 22:40:38
HWK: 2011-09-01 11:50:04

What a shame. I have to apologize again. In some solutions the coordinates could be 'nan' what my judge didn't recognize. I changed this. Thus Daniel Hui's leading, but not really good solution results now properly in WA. Sorry again.

HWK: 2011-09-01 11:50:04

I've hidden the problem for a short time to make some changes. It seems that all your comments are lost thereby. Sorry!
But thanks to your comments I changed the judge again. I hope everybody is satisfied now and the problem is worth to stay in challenge.

@bcurcio, @Robert Gerbicz: Please submit your solutions again. It seems that rejudging fudge the results. I will disqualify all solutions. Sorry again for inconvenience.

Last edit: 2011-08-16 17:21:05

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