071 - Linear Programming Editorial /

Time Limit: 10 sec / Memory Limit: 1024 MB

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