配点: 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