首先要将这个图连通，方法是通过扫描线+set求出每个连通块最高的点上方的第一条边，然后向交点连边。
然后把边拆成两条双向边，每次找到一条没走过的边，找到极角排序后它的反向边的后继，直到回到这条边。
根据叉积可以求出面积，如果面积非负，那么就说明找到了一个封闭区域。
然后再进行一次扫描线，找到一个点上方最低的边，即可完成点定位。
时间复杂度$O(m\log m)$。
求出对偶图之后，暴力枚举所有必须保护的古迹，建图求最小割即可。
#include<cstdio>
#include<cmath>
#include<set>
#include<algorithm>
using namespace std;
const double eps=1e-8,inf=1000000010;
const int N=510,M=50010,INF=~0U>>2;
int n,m,q,cnt,i,x,y,z;
inline int sgn(double x){
if(fabs(x)<eps)return 0;
return x>0?1:-1;
}
struct P{
double x,y;
P(){}
P(double _x,double _y){x=_x,y=_y;}
double operator*(const P&b){return x*b.y-y*b.x;}
}a[N],b[N];
struct E{
int x,y,z;double o;
E(){}
E(int _x,int _y,int _z=-1){x=_x,y=_y,z=_z,o=atan2(a[y].x-a[x].x,a[y].y-a[x].y);}
}e[M];
bool del[M],ex[M];int from[M],id[N];
struct EV{
double x;int y,t;
EV(){}
EV(double _x,int _y,int _t){x=_x,y=_y,t=_t;}
}ev[M<<1];
inline bool cmpEV(const EV&a,const EV&b){
if(sgn(a.x-b.x))return a.x<b.x;
return a.t<b.t;
}
namespace GetArea{
struct cmp{bool operator()(int a,int b){return e[a].o<e[b].o;}};
set<int,cmp>g[N];set<int,cmp>::iterator k;int i,j,q[M],t;
void work(){
for(i=0;i<m+m;i++)if(!del[i]&&!ex[i]){
for(q[t=1]=j=i;;q[++t]=j=*k){
k=g[e[j].y].find(j^1);k++;
if(k==g[e[j].y].end())k=g[e[j].y].begin();
if(*k==i)break;
}
double s=0;
for(j=1;j<=t;j++)s+=a[e[q[j]].x]*a[e[q[j]].y],del[q[j]]=1;
if(sgn(s)<0)continue;
for(cnt++,j=1;j<=t;j++)from[q[j]]=cnt;
}
}
}
namespace ScanLine{
struct cmp{
bool operator()(int A,int B){
if(e[A].x==e[B].x)return e[A].o>e[B].o;
double x=min(a[e[A].x].x,a[e[B].x].x),
yA=(a[e[A].x].y-a[e[A].y].y)*(x-a[e[A].y].x)/(a[e[A].x].x-a[e[A].y].x)+a[e[A].y].y,
yB=(a[e[B].x].y-a[e[B].y].y)*(x-a[e[B].y].x)/(a[e[B].x].x-a[e[B].y].x)+a[e[B].y].y;
return yA>yB;
}
};
set<int,cmp>T;
int cnt,i,j,k,g[M],v[M],nxt[M],ed,vis[N],t,tmp[N];
inline bool cmpC(int x,int y){return a[x].x<a[y].x;}
inline void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}
void dfs(int x){
vis[x]=1;
if(a[x].y>a[t].y)t=x;
for(int i=g[x];i;i=nxt[i])if(!vis[v[i]])dfs(v[i]);
}
inline double cal(int A,double x){
return(a[e[A].x].y-a[e[A].y].y)*(x-a[e[A].y].x)/(a[e[A].x].x-a[e[A].y].x)+a[e[A].y].y;
}
void connect(){
for(i=0;i<m+m;i++)add(e[i].x,e[i].y);
for(i=1;i<=n;i++)if(!vis[i])dfs(t=i),ev[cnt++]=EV(a[t].x,t,2);
for(i=0;i<m+m;i++)if(sgn(a[e[i].x].x-a[e[i].y].x)>0){
ev[cnt++]=EV(a[e[i].y].x,i,1);
ev[cnt++]=EV(a[e[i].x].x,i,0);
}
sort(ev,ev+cnt,cmpEV);
a[n+1]=P(inf,inf);
a[n+2]=P(-inf,inf);
e[m+m]=E(n+1,n+2);
T.insert(m+m);
e[m+m+1]=E(n+2,n+1);
n+=2,m++;
for(ed=0,i=1;i<=n;i++)g[i]=0;
for(i=0;i<cnt;i++){
if(ev[i].t==0)T.erase(ev[i].y);
if(ev[i].t==1)T.insert(ev[i].y);
if(ev[i].t==2){
a[n+1]=P(ev[i].x,a[ev[i].y].y+eps);
a[n+2]=P(ev[i].x-1,a[ev[i].y].y+eps);
e[m+m]=E(n+1,n+2);
T.insert(m+m);
set<int,cmp>::iterator j=T.find(m+m);
j--,add(*j,ev[i].y);
T.erase(m+m);
}
}
int newm=m+m;
for(i=0;i<m+m;i++){
for(cnt=0,j=g[i];j;j=nxt[j]){
if(!sgn(a[v[j]].x-a[e[i].x].x)){
e[newm++]=E(v[j],e[i].x);
e[newm++]=E(e[i].x,v[j]);
continue;
}
if(!sgn(a[v[j]].x-a[e[i].y].x)){
e[newm++]=E(v[j],e[i].y);
e[newm++]=E(e[i].y,v[j]);
continue;
}
tmp[++cnt]=v[j];
}
if(!cnt)continue;
ex[i]=ex[i^1]=1;
sort(tmp+1,tmp+cnt+1,cmpC);
for(k=e[i].y,j=1;j<=cnt;k=n,j++){
a[++n]=P(a[tmp[j]].x,cal(i,a[tmp[j]].x));
e[newm++]=E(k,n,e[i].z);
e[newm++]=E(n,k,e[i].z);
e[newm++]=E(tmp[j],n,e[i].z);
e[newm++]=E(n,tmp[j],e[i].z);
}
e[newm++]=E(n,e[i].x,e[i].z);
e[newm++]=E(e[i].x,n,e[i].z);
}
m=newm/2;
}
void location(){
for(i=cnt=0;i<m+m;i++)if(!ex[i]&&sgn(a[e[i].x].x-a[e[i].y].x)>0){
ev[cnt++]=EV(a[e[i].y].x,i,1);
ev[cnt++]=EV(a[e[i].x].x,i,0);
}
for(i=0;i<q;i++)ev[cnt++]=EV(b[i].x,i,2);
sort(ev,ev+cnt,cmpEV);
T.clear();
for(i=0;i<cnt;i++){
if(ev[i].t==0)T.erase(ev[i].y);
if(ev[i].t==1)T.insert(ev[i].y);
if(ev[i].t==2){
a[n+1]=P(ev[i].x,b[ev[i].y].y);
a[n+2]=P(ev[i].x-1,b[ev[i].y].y);
e[m+m]=E(n+1,n+2);
T.insert(m+m);
set<int,cmp>::iterator j=T.find(m+m);
if(j!=T.begin())j--,id[ev[i].y]=from[*j];
T.erase(m+m);
}
}
}
}
namespace MinCut{
struct E{int t,f;E*nxt,*pair;}*g[N],*d[N],pool[M],*cur;
int mask,m,val[M],st[M],en[M],S,T,h[N],gap[N],maxflow,ans[N];
inline void add(int s,int t,int f){
E*p=cur++;p->t=t;p->f=f;p->nxt=g[s];g[s]=p;
p=cur++;p->t=s;p->f=0;p->nxt=g[t];g[t]=p;
g[s]->pair=g[t];g[t]->pair=g[s];
}
int sap(int v,int flow){
if(v==T)return flow;
int rec=0;
for(E*p=d[v];p;p=p->nxt)if(h[v]==h[p->t]+1&&p->f){
int ret=sap(p->t,min(flow-rec,p->f));
p->f-=ret;p->pair->f+=ret;d[v]=p;
if((rec+=ret)==flow)return flow;
}
if(!(--gap[h[v]]))h[S]=T;
gap[++h[v]]++;d[v]=g[v];
return rec;
}
void work(){
for(i=1;i<=q;i++)ans[i]=INF;
S=cnt+1;T=S+1;
for(i=0;i<m;i++){
if(!st[i])st[i]=T;
if(!en[i])en[i]=T;
}
for(mask=1;mask<1<<q;mask++){
for(cur=pool,i=0;i<=T;i++)g[i]=d[i]=NULL,h[i]=gap[i]=0;
for(i=0;i<m;i++)add(st[i],en[i],val[i]),add(en[i],st[i],val[i]);
for(i=0;i<q;i++)if(mask>>i&1)add(S,id[i],INF);
for(gap[maxflow=0]=T,i=1;i<=T;i++)d[i]=g[i];
while(h[S]<T)maxflow+=sap(S,INF);
ans[__builtin_popcount(mask)]=min(ans[__builtin_popcount(mask)],maxflow);
}
for(i=1;i<=q;i++)printf("%d\n",ans[i]);
}
}
int main(){
scanf("%d%d%d",&q,&n,&m);
MinCut::m=m;
for(i=0;i<q;i++)scanf("%lf%lf",&b[i].x,&b[i].y);
for(i=1;i<=n;i++)scanf("%lf%lf",&a[i].x,&a[i].y);
for(i=0;i<m;i++){
scanf("%d%d%d",&x,&y,&MinCut::val[i]);
e[i<<1]=E(x,y,i);
e[i<<1|1]=E(y,x,i);
}
ScanLine::connect();
for(i=0;i<m+m;i++)if(!ex[i])GetArea::g[e[i].x].insert(i);
GetArea::work();
ScanLine::location();
for(i=0;i<m+m;i++)if(!ex[i]&&~e[i].z){
MinCut::st[e[i].z]=from[i];
MinCut::en[e[i].z]=from[i^1];
}
MinCut::work();
return 0;
}