分数: 800 点
问题陈述
有 N 行 xy- 平面。 i第行表示为 A_ix+B_iy=C_i。 其中任意两行 N+2 行,以上 N 行加上 x- 轴和 y- 轴,恰好在一个点处相互交叉。
对于每对 1 \leq i < j \leq N,在十字路口有一辆车 i-th 和 j第行。 即使三条或多条线相交于一点,也会为每对线单独放置一辆车。 也就是说,将会有 k(k-1)/2 车辆放置在十字路口 k 行。
那些车已经很旧了,只能平行于 x- 轴或 y- 轴。
高桥将在高桥的一个地方举办古董车展览 xy- 平面。 为了避免对半破损的汽车造成太大损坏,他会选择展览地点,以便所有汽车都移动到该地点时,所走的总距离最小。 如果这样的地方不唯一确定,则在满足上述条件的地方中,取最小的地方 x- 将选择坐标。 如果仍未唯一确定,则在满足上述两个条件的地方中,选择最小的地方 y- 将选择坐标。
找到将要选择的展览地点。
约束
- 2 \leq N \leq 4 × 10^4
- 1 \leq |A_i|,|B_i| \leq 10^4(1 \leq i \leq N)
- 0 \leq |C_i| \leq 10^4(1 \leq i \leq N)
- 没有两条给定的直线是平行的。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N A_1 B_1 C_1 : A_N B_N C_N
输出
打印 x- 坐标和 y- 将选择的展览地点的坐标,按此顺序,中间有一个空格。当绝对误差或相对误差最大时,判定输出正确 10^{-9}.
示例输入 1
3 1 1 1 2 -1 2 -1 2 2
示例输出 1
1.000000000000000 1.000000000000000

图中蓝色圆圈所示的每个地方都有一辆车。要选择的位置由紫色圆圈显示。
示例输入 2
4 1 1 2 1 -1 0 3 -1 -2 1 -3 4
示例输出 2
-1.000000000000000 -1.000000000000000
示例输入 3
7 1 7 8 -2 4 9 3 -8 -5 9 2 -14 6 7 5 -8 -9 3 3 8 10
示例输出 3
-1.722222222222222 1.325000000000000