题目
Description
吉丽的漫展有n件手办和m名警卫。建立平面直角坐标系，每个手办和警卫都可以看做一个点。警卫们的目光都朝着y轴负方向，且都有相同大小的视角。警卫可以看见自己视角内（包括边界上的点）的所有手办，不用考虑视线的遮挡。 你打算抢劫吉丽的漫展，但不可被警卫发现。为了实施这次抢劫计划，你可以事先贿赂某些警卫，让他们闭上眼睛。只要某件手办不在任何睁着眼睛的警卫的视野内，你就可以偷走它。你知道每件手办的价格，以及每位警卫需要接受多少钱的贿赂。你想知道自己的最大收益是多少。
Input
第一行两个整数n,m(1<=n,m<=200000)，分别表示手办的数量和警卫的数量。 第二行两个整数w,h(1<=w,h<=10^9)，表示每个警卫的视角的一半的正切值是w/h。（见配图） 接下来n行，每行三个整数x[i],y[i],vi，表示手办的坐标为(x[i],y[i])，价格为v[i]。 接下来m行，格式同上，表示警卫的坐标为(x[i],y[i])，需接受贿赂的金额为v[i]。 保证每个点最多只有一个手办或一个警卫。
Output
输出仅一行表示最大收益。
Sample Input
5 3
2 3
2 6 2
5 1 3
5 5 8
7 3 4
8 6 1
3 8 3
4 3 5
5 7 6
Sample Output
6
样例解释：
贿赂3+6元，偷走2+8+4+1元，收益6元。
题解
如果处理出每个警卫和每个手办的关系，就可以最小割解决虽然复杂度不对先不管
因为警卫的视野角都一样，可以旋转坐标系并拉伸单位长度，使得警卫的视角为$90°$且方向为右下角，这样警卫$(x,y)$可以影响到的手办$(x’,y’)$满足条件为$x’\ge x,y’\le y$
$2e5$的数据肯定不能跑网络流了，发现这个题横坐标越小能影响的范围越大，可以把警卫和手办都按横坐标从大到小排序，如果遇到的是手办，就加入查询集合；如果是警卫，这时候流量流向查询集合中第一个纵坐标小于它的手办肯定比流向其他的优，因为限制最大，流满了就把手办从集合里去掉
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<set>
# include<algorithm>
# define X first
# define Y second
# define LL long long
# define mp make_pair
# define Pi pair<LL,int>
using namespace std;
const int MAX=4e5+5;
struct p{
LL x,y;
int v;
bool fl;
bool operator< (const p &a)
const{
if(x!=a.x) return x>a.x;
return y<a.y;
}
}a[MAX];
int n,m,Q,w,h;
LL ans;
set<Pi> s;
int read()
{
int x=0,fl=1;
char ch=getchar();
for(;!isdigit(ch);fl=(ch=='-')?-1:1,ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x*fl;
}
int main()
{
n=read(),m=read(),w=read(),h=read();
for(int i=1,x,y;i<=n;++i)
x=read(),y=read(),a[i].x=1ll*x*h-1ll*y*w,a[i].y=1ll*x*h+1ll*y*w,ans+=(a[i].v=read());
for(int i=1,x,y;i<=m;++i)
x=read(),y=read(),a[i+n].x=1ll*x*h-1ll*y*w,a[i+n].y=1ll*x*h+1ll*y*w,a[i+n].v=read(),a[i+n].fl=1;
sort(a+1,a+1+n+m);
for(int i=1,x;i<=n+m;++i)
if(!a[i].fl) s.insert(mp(-a[i].y,a[i].v));
else if(a[i].fl) while(a[i].v)
{
set<Pi>::iterator A=s.lower_bound(mp(-a[i].y,-2e9));
if(A==s.end()) break;
Pi T=*A;
s.erase(T),x=min(a[i].v,T.Y),a[i].v-=x,T.Y-=x,ans-=x;
if(T.Y) s.insert(T);
}
return printf("%lld",ans),0;
}
