Station

发布时间: 2017年12月10日 22:15   最后更新: 2017年12月10日 22:18   时间限制: 5000ms   内存限制: 512M

Now FSX is in charge of many sea routes. Each route can be represented as a line in the form of Ax+By=C in the two-dimensional plane. Altogether there are n routes and they are neither parallel to each other nor parallel to the coordinate axis. So every two routes have an intersection and in all there are n(n-1)/2 intersection points( suppose they are P_1,P_2,..,P_(n-1)n/2 ) . Intersections can be very dangerous so FSX needs to build a station in a point Q(X_Q,Y_Q) to manage these intersections. For convenience,FSX wants the sum of the Manhattan distance between Q and every P_i as small as possible. The defination of Manhattan distance between two points A(X_a,Y_a), B(X_b,Y_b) is |X_a - X_b| + |Y_a - Y_b|.

Can you help him find the optimal coordinate of Q? Note if there are multiple solutions, output the one with the smallest x-coordinate. If there are still multiple solutions, output the one with the smallest y-coordinate.

Input starts with an integer T(T<=30), denoting the number of test cases.
For each test case:
The first line contains an integer n (2<=n<=40000), indicating the number of routes.
For the next n lines, each line contains 3 integers Ai, Bi, Ci, (1<=|Ai|,|Bi|<=10^4, 0<=|Ci|<=10^4) , indicating a route in the form of Aix+Biy=Ci.
There are only 2 test cases that n > 1000.

For each test case, print one line with two floating numbers x,y, both rounded to 5 digits after the decimal point, denoting the coordinate of the station.

复制
2
3
1 1 1
2 -1 2
-1 2 2
4
1 1 2
1 -1 0
3 -1 -2
1 -3 4
1.00000 1.00000
-1.00000 -1.00000

For the first test case, we can choose (1,1) as the station since the sum of Manhattan distance between it and the 3 intersections (0,1),(1,0),(2,2) equals 4.

图片1.png

2017 fdu-icpc

2017 Fudan ACM-ICPC 程序设计校赛现场赛