2D Linear Programming
Time Limit : 10 Second
Memory Limit : 128 MB
Special Judge
Submission: 38
Solved: 6
- Description
- This Problem is special judge.
Given n constraints:
a1 x + b1 y <= c1
a2 x + b2 y <= c2
......
an x + bn y <= cn
Your goal is to maximize z = ux + vy. - Input
- The first line is an integer T, indicates the number of test cases.
The first line of each test case contains an interger n( n <= 100000 ), 2 float numbers u, v( -10000 < u, v < 10000 ), followed by n lines, each line contains 3 real numbers ai bi ci.
If the feasible region exists, you can assume -1e10 < max{ z } < 1e10 and for any point P in the feasible region, you can assume -100000 <= Px, Py <= 100000. - Output
- For each test case, output a floating number, the maximum value of z = ux + vy. If is no feasible solutions at all, just output "infeasible". Numbers must be precise up to 10e-3.
- sample input
-
2 2 1 1 1 0 1 0 1 1 2 1 1 1 0 1 -1 0 -2
- sample output
-
2.00000000 infeasible
- hint
- source
- INFINITE_Li