1334 - 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
© 2015 HUST ACMICPC TEAM. All Right Reserved.