← 返回题目列表

AtCoder · math_and_algorithm_bf

071. 线性规划

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

配点: 1000 点

問題文

正整数N和一对正整数 给出了(a_1,b_1,c_1),(a_2,b_2,c_2), ... , (a_N,b_N,c_N)。 满足以下所有条件表达式的一组实数 在(x,y)中, 编写一个程序来查找x+y的最大值。 当

  • a_1 x + b_1 y \leq c_1
  • a_2 x + b_2 y \leq c_2
  • (中略)
  • a_N x + b_N y \leq c_N

制約

  • 1 \leq N \leq 500
  • 1 \leq a_i,b_i,c_i \leq 10^9
  • x+y最大时,x和 在y都是正实数

这个约束是\mathcal{O}(N^3)允许及时求解的约束。 请输出


入力

输入是按以下格式从标准输入给出的。

N
a_1 b_1 c_1
a_2 b_2 c_2
.
.
a_N b_N c_N

出力

x+y的最大值。 请注意,预期答案的绝对误差或相对误差为 10^{−6} 如果答案如下,则视为正确。


入力例 1

2
1 3 3
3 1 3

出力例 1

1.5