维护凸包求调

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct line{
	int a,b,c;
	long double k;
	long double xp;//x轴交点
	long double yp;//y轴交点 
} lines[110];
/*
ax + by <= c
by <= -ax + c
y <= (-a / b)x + c/b
y = (-a/b)x +c/b;
x = 1 y = (c - a)/b
y = 1 x = (c - b)/a
*/
bool cmp(line a,line b){
	return a.k > b.k;
}
int S[110],sp;
long double calc(int i1,int i2){
	line l1 = lines[i1],l2 = lines[i2];
	long double x = (1.00*l1.c / l1.b - 1.00 * l2.c / l2.b)/(1.00*l1.a / l1.b - 1.00 * l2.a / l2.b);
	long double y = (1.00*l1.c / l1.a - 1.00 * l2.c / l2.a)/(1.00*l1.b / l1.a - 1.00 * l2.b / l2.a);
	
	return x + y;
}
void solve(){
	int n,C,M;
	cin>>n>>C>>M;
	memset(lines,0,sizeof(lines));
	lines[1] = {1,0,C,-2e10,C,2e10};
	lines[n+2] = {0,1,M,0,2e10,M};
	for(int i = 2;i<=n+1;i++){
		cin>>lines[i].a>>lines[i].b>>lines[i].c;
		lines[i].k = -1.00 * lines[i].a / lines[i].b;
		lines[i].xp = ((long double)lines[i].c - lines[i].b)/lines[i].a;
		lines[i].yp = ((long double)lines[i].c - lines[i].a)/lines[i].b;
	}
	sort(lines+1,lines+1+n+2,cmp);
	sp = 0;
	S[++sp] = 1;
	for(int i = 2;i<=n+2;i++){
		if(lines[i].xp >= lines[S[sp]].xp){
			continue;
		}
		while(sp && lines[S[sp]].yp >= lines[i].yp){
			sp--;
		}
		S[++sp] = i;
	}
	
	int anst = (max(lines[S[1]].yp,lines[S[sp]].xp));
	for(int i = 2;i<=sp;i++){
		anst = max(anst,(int)(calc(S[i-1],S[i])));
	}
	cout<<C+M-anst<<'\n';
}
signed main(){
	int T;
	cin>>T;
	while(T--){
		solve();
	}
}