← 返回题目列表

AtCoder · tenka1_2017_e

E. 笛卡尔坐标

中文机器翻译题面 查看原题

分数: 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