题意
给(n)个三元组(a_i,b_i,c_i)，以及(m)个查询(s,t)
求使得(sumlimits a_ix_i=s,sumlimits b_ix_i=t)的同时(sumlimits c_ix_i)最大（({x})为非负实数）
(nle 10^5,mle 10^4)，(1le a,b,c,s,tle 10^4)（均为整数）
做法
[egin{aligned}
&max~~sum c_ix_i\
&s.t.egin{cases}sum a_ix_i=s\
sum b_ix_i=t\
xge 0\
end{cases}
end{aligned}]
相当于
[egin{aligned}
&max~~sum c_ix_i\
&s.t.egin{cases}sum a_ix_ile s\
-sum a_ix_ile -s\
sum b_ix_ile t\
-sum b_ix_ile -t\
xge 0\
end{cases}
end{aligned}]
对偶一下
[egin{aligned}
&min~~sy_1-sy_2+ty_3-ty_4\
&egin{cases}forall i,s.t.a_iy_1-a_iy_2+b_iy_3-b_iy_4le c_i\
y_1,y_2,y_3,y_4ge 0\
end{cases}
end{aligned}]
令(x'=y_1-y_2,y'=y_3-y_4)
[egin{aligned}
&min~~sx+ty\
&forall i,s.t. a_ix+b_iyle c_i
end{aligned}]
可以预处理半平面交，然后三分去且凸壳，可以利用以下性质判断是否无解
无界性：若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解