【传送门：BZOJ1822】
简要题意：
有n个女巫，m个精灵，k棵树，每个女巫每次释放魔法可以消灭一个精灵，施法间隔（CD）为R，可以在第0秒的时候直接施法
然而每个女巫只能消灭与自己距离<=施法距离，并且视线没有被任何一棵树遮挡
每棵树给出它的半径，只要一个女巫与精灵的连线与这棵树所形成的圆有交点，则这个女巫无法消灭该精灵
求出最小时间消灭所有精灵，如果不能消灭所有精灵，则输出-1
题解：
首先用计算几何来计算女巫可以消灭那些精灵
先判断距离，然后如果圆心离这两个点的距离小于等于半径 或者 圆心向连线作垂线段的长小于等于半径且垂足在连线上，那么女巫无法消灭精灵
怎么判断圆心向连线作垂线段的长小于等于半径且垂足在连线上？
先用叉积求出三角形面积，然后求高，因为直角三角形a*a+b*b=c*c，钝角三角形a*a+b*b<c*c，锐角三角形a*a+b*b>c*c
如果垂足不在连线上，那么圆心分别与两个点的连线，和两个点之间的连线所形成的三角形一定是钝角三角形，那么只要不是垂足就在连线上了
然后二分答案，网络流判断，注意所有女巫在第0秒的时候都可以攻击
对于-1的情况，就是只要在计算女巫可以消灭那些精灵后，看一下每个精灵是否能够被消灭就可以了
参考代码：
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<cstdlib> using namespace std; struct node { int x,y,c,next,other; }a[210000];int len,last[410]; void ins(int x,int y,int c) { int k1=++len,k2=++len; a[k1].x=x;a[k1].y=y;a[k1].c=c; a[k1].next=last[x];last[x]=k1; a[k2].x=y;a[k2].y=x;a[k2].c=0; a[k2].next=last[y];last[y]=k2; a[k1].other=k2; a[k2].other=k1; } int h[410],list[410],st,ed; bool bt_h() { memset(h,0,sizeof(h)); h[st]=1; int head=1,tail=2; list[1]=st; while(head!=tail) { int x=list[head]; for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(h[y]==0&&a[k].c>0) { h[y]=h[x]+1; list[tail++]=y; } } head++; } if(h[ed]==0) return false; else return true; } int findflow(int x,int f) { if(x==ed) return f; int s=0,t; for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(h[y]==(h[x]+1)&&a[k].c>0&&f>s) { t=findflow(y,min(a[k].c,f-s)); s+=t; a[k].c-=t;a[a[k].other].c+=t; } } if(s==0) h[x]=0; return s; } struct wm { double x,y; int r,t; }w[210],c[210],tr[210]; bool map[210][210]; double dis(wm a,wm b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } double gg(wm a,wm b) { return a.x*b.x+a.y*b.y; } double multi(wm p1,wm p2,wm p0) { double x1,x2,y1,y2; x1=p1.x-p0.x; y1=p1.y-p0.y; x2=p2.x-p0.x; y2=p2.y-p0.y; return x1*y2-x2*y1; } bool bo[210]; int n,m; bool check(int x) { len=0;memset(last,0,sizeof(last)); for(int i=1;i<=n;i++) { ins(st,i,x/w[i].t+1); } for(int i=1;i<=m;i++) { ins(i+n,ed,1); } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(map[i][j]==true) { ins(i,j+n,1); } } } int ans=0; while(bt_h()==true) ans+=findflow(st,999999999); if(ans==m) return true; else return false; } int main() { int T; scanf("%d%d%d",&n,&m,&T); st=0;ed=n+m+1; for(int i=1;i<=n;i++) scanf("%lf%lf%d%d",&w[i].x,&w[i].y,&w[i].r,&w[i].t); for(int i=1;i<=m;i++) scanf("%lf%lf",&c[i].x,&c[i].y); for(int i=1;i<=T;i++) scanf("%lf%lf%d",&tr[i].x,&tr[i].y,&tr[i].r); memset(map,true,sizeof(map)); memset(bo,false,sizeof(bo)); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(w[i].r<dis(w[i],c[j])){map[i][j]=false;continue;} bool bk=true; for(int t=1;t<=T;t++) { if(dis(w[i],tr[t])<=tr[t].r||dis(c[j],tr[t])<=tr[t].r){bk=false;break;} double s=abs(multi(w[i],c[j],tr[t])); double h=s/dis(w[i],c[j]); double d1=dis(w[i],c[j]),d2=dis(w[i],tr[t]),d3=dis(c[j],tr[t]); if(h<=double(tr[t].r)&&max(d2,d3)*max(d2,d3)<=min(d2,d3)*min(d2,d3)+d1*d1){bk=false;break;} } if(bk==false) map[i][j]=false; else bo[j]=true; } } for(int i=1;i<=m;i++) if(bo[i]==false){printf("-1 ");return 0;} int l=0,r=1<<31-1,ans; while(l<=r) { int mid=(l+r)/2; if(check(mid)==true) { ans=mid; r=mid-1; } else l=mid+1; } printf("%d ",ans); return 0; }