APP
首先考虑解决一个子问题：如何判断答案是否是 (0)。假设 Bob 的多边形是 (P)，水母没有活动区域，那么显然只有当水母在 (P) 中时 Bob 才会被蜇。换而言之，假设会使 Bob 被蜇的区域为禁止区域，那么这个禁止区域就是每只水母周围的多边形。考虑再加上水母半径为 (r) 的活动范围，类似于【JSOI2018】战争，禁止区域为多边形 (-P) 与半径为 (r) 的圆的闵可夫斯基和。
由于会出现两只水母的活动范围有重叠的情况，此时 Bob 便不能从这两只水母之间通过。具体的，假设这两只水母的活动区域分别为 (r_1) 和 (r_2)，中心分别为 ((x_1,y_1)) 和 ((x_2,y_2))，如果 ((x_1-x_2,y_1-y_2)) 在 (P) 与半径为 (r_1+r_2) 的圆的闵可夫斯基和中，Bob 便不能经过这两只水母之间。实现上可以通过找该向量到 (P) 与 (-P) 的闵可夫斯基和的距离与 (r_1+r_2) 进行比较即可。需要注意的是题目所给定条件可以让两者相对精度差到 (10^{-17}) 左右，因此不能直接用浮点数计算。
并且注意到可以在泳池边界和水母之间经过。考虑构造一个图，令边界和每只水母都是顶点，如果两只水母之间不能经过这两个顶点就连一条边（可以发现这就是对偶图）。如果平面图上下连通（答案为 (0)），这就相当于对偶图左边界对应点于右边界对应点不连通。否则如果连通，则 Bob 一定会被蛰。
然后考虑原来问题，我们所要求的就是删去尽量少的水母，使 Bob 不被蛰。这是一个标准的网络流形式：求最小割点数量。将原图中水母所对应的顶点拆成两个点，连一条容量为 (1) 的边，然后直接跑最小割就行了。
#include<bits/stdc++.h>
#define int long long
#define ll long long
#define R(i,a,b) for(int i=(a),i##E=(b);i<=i##E;i++)
#define L(i,a,b) for(int i=(b),i##E=(a);i>=i##E;i--)
using namespace std;
const ll inf=1ll<<30;
int n,w,m;
struct point
{
int x,y;
inline point (int X=0,int Y=0):x(X),y(Y) {}
inline point operator +(const point &A)const
{
return point(x+A.x,y+A.y);
}
inline point operator -(const point &A)const
{
return point(x-A.x,y-A.y);
}
inline ll dot(const point &A)
{
return 1ll*x*A.x+1ll*y*A.y;
}
inline ll det(const point &A)
{
return 1ll*x*A.y-1ll*y*A.x;
}
inline int operator <(const point &A)const
{
return x==A.x?y<A.y:x<A.x;
}
inline ll abs2()
{
return 1ll*x*x+y*y;
}
};
vector<point>a,b;
int top;
int tim,S,T,id[222][2];
struct ccl
{
point o;
int r;
};
vector<ccl>c;
int lb,rb;
inline vector<point> init(vector<point> a)
{
vector<point>t;
int p=min_element(a.begin(),a.end())-a.begin();
R(i,0,a.size()-1) t.emplace_back(a[(i+p)%a.size()]);
return t;
}
inline vector<point> mincowski(vector<point>a,vector<point>b)
{
a=init(a),b=init(b);
vector<point>t,A(a.size()),B(b.size());
R(i,0,a.size()-1) A[i]=a[(i+1)%a.size()]-a[i];
R(i,0,b.size()-1) B[i]=b[(i+1)%b.size()]-b[i];
int i=0,j=0;
t.emplace_back(a[0]+b[0]);
while(i<a.size()||j<b.size())
{
if(i==a.size()) t.emplace_back(t.back()+B[j]),++j;
else if(j==b.size()) t.emplace_back(t.back()+A[i]),++i;
else if(A[i].det(B[j])>=0) t.emplace_back(t.back()+A[i]),++i;
else t.emplace_back(t.back()+B[j]),++j;
}
t.pop_back();
return t;
}
inline int check_onseg(point p,point x,point y)
{
return ((p-x).det(p-y))==0&&((p-x).dot(p-y))<=0;
}
inline int check(point a,ll r,vector<point>q)
{
for(auto b:q) if((a-b).abs2()<r*r) return 1;
int ok=1;
R(i,0,q.size()-1)
{
point x=q[i],y=q[(i+1)%q.size()];
if(check_onseg(a,x,y)) return 1;
if((a-x).dot(y-x)>0&&(a-y).dot(x-y)>0)
{
ll t=(a-x).det(y-x);
if(t*t<r*r*(y-x).abs2()) return 1;
}
ok&=((a-x).det(y-x)<=0);
}
return ok;
}
struct edge
{
int to,nxt,f;
}e[166666];
int head[444],dis[444],cnt=1;
int q[444];
inline void add_edge(int u,int v,int d)
{
e[++cnt]=(edge){v,head[u],d};
head[u]=cnt;
e[++cnt]=(edge){u,head[v],0};
head[v]=cnt;
}
int bfs()
{
memset(dis,-1,sizeof(dis));
int h=0,t=1;
q[1]=S;dis[S]=0;
while(h!=t)
{
int u=q[++h];
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
if(dis[v]==-1&&e[i].f)
{
dis[v]=dis[u]+1;
if(v==T) return 1;
q[++t]=v;
}
}
}
return 0;
}
int dfs(int u,int flow)
{
if(u==T) return flow;
int del=flow;
for(int i=head[u];i&&del;i=e[i].nxt)
{
int v=e[i].to;
if(dis[v]==dis[u]+1&&e[i].f)
{
int k=dfs(v,min(e[i].f,del));
e[i].f-=k;
e[i^1].f+=k;
del-=k;
}
}
if(del) dis[u]=-1;
return flow-del;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>w;
lb=166666,rb=-166666;
a.resize(n),b.resize(n);
R(i,0,n-1)
{
int x,y;
cin>>x>>y;
a[i]=point(x,y),b[i]=point(-x,-y);
lb=min(lb,x),rb=max(rb,x);
}
cin>>m;
R(i,1,m) id[i][0]=++tim,id[i][1]=++tim;
S=++tim;
T=++tim;
c.resize(m+1);
R(i,1,m) cin>>c[i].o.x>>c[i].o.y>>c[i].r;
a=mincowski(a,b);
R(i,1,m)
{
add_edge(id[i][0],id[i][1],1);
if(rb-lb>c[i].o.x-c[i].r) add_edge(S,id[i][0],inf);
if(rb-lb>w-c[i].o.x-c[i].r) add_edge(id[i][1],T,inf);
}
R(i,1,m) R(j,i+1,m) if(check(c[i].o-c[j].o,c[i].r+c[j].r,a))
{
add_edge(id[j][1],id[i][0],inf);
add_edge(id[i][1],id[j][0],inf);
}
int ans=0;
while(bfs()) ans+=dfs(S,inf);
cout<<ans<<'
';
}
本文摘自 ：https://www.cnblogs.com/
