20001. 2-Dimensional Linear Programming (Design Strategies for Computer Algorithms)

I'm a slow walker, but I never walk backwards.

輸入格式

輸入有多組測資。

每組測資第一行為一個正整數 $N$ ($N \le 10000$),代表以下限制條件的個數,每個限制條件有三個整數 $a$, $b$, $c$,表示 $ax + by \le c$。

輸出格式

對於每組測資,請輸出滿足所有限制條件的最小 $y$ 值。若沒有解,請輸出 NA,若為負無限大,請輸出 -INF

絕對誤差在 $10^{-3}$ 內都算正確。

範例輸入

9
6 -21 108
-9 11 123
-4 -1 18
3 -1 54
3 1 54
12 17 216
2 5 36
-1 4 47
-7 3 79
9
1 1 10
7 -3 68
6 6 27
6 7 54
6 -4 36
-1 -1 -20
-5 9 36
4 -6 54
-4 11 78

範例輸出

-6.000000
NA

Discussion