提示: 欢迎访问OurACM平台。
Problem 1576 石油管道

Accept: 75    Submit: 417
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

Oaiei居住在A城市,并且是这个城市建设的总设计师。最近有个问题一直困恼着他。A城市里有三个大型工厂,每个大型工厂每天都需要消耗大量的石油,现在城市里要建设一个石油中转站,从石油中转站到三个大型工厂都需要铺设石油管道。现在你的问题来了,应该如何建设这个石油中转站,使得石油中转站到三个大型工厂所需要铺设的石油管道线路最短,你能够帮助他吗?

设石油中转站B的坐标为(X,Y),三个大型工厂的坐标分别为C(X1,Y1),D(X2,Y2),E(X3,Y3),所输要铺设的石油管道线路总长为distance(B,C)+distance(B,D)+distance(B,E),其中distance(A,B)表示A,B两点之间的欧几里德距离。

Input

第一行为一个整数C(1<=C<=200),表示测试数据的组数。
以下C行,每行6个整数,分别表示C、D、E点 (X,Y)的坐标。注意:B点的选址可以与C、D、E点相重合。

Output

对于每个输入数据,输出一行两个数M1,M2,中间用一个空格分隔开。M1,M2分别四舍五入到小数点后两位,表示石油中转站的坐标。

Sample Input

1 0.00 0.00 1.00 0.00 0.00 1.00

Sample Output

0.21 0.21

Source

FOJ月赛-2008年3月

Submit  Back  Status  Discuss