暴力枚举 + 计算几何 + 二分 + 网络流
暴力枚举
先枚举判断每个精灵都能被谁杀死,用二维数组存状态,
遇到不能被杀死的精灵就输出 -1 结束。
几何
判断过程中先看有没有树:
没树
就直接判断巫妖能不能攻击到精灵。
有树
用点到直线距离算出距离和垂足,判断垂足在不在巫妖和精灵之间;如果不在 就直接判断巫妖能不能攻击到精灵;如果在 比较树的半径和距离;
二分
在0~最短的杀死所有精灵的时间内,杀死精灵数随时间单调递增,则可以二分最短的杀死所有精灵的时间。
网络流检验
符合最大流的流量守恒和容量限定,求最多杀死的精灵数的最大流。
建图:源点到巫妖建边,容量为可杀死精灵数;精灵到汇点建边,容量为 1;巫妖到可杀死的精灵建边,容量为 1;
建完图之后,跑一遍 dinic 检验答案。
代码
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define ll long long
const int N=10010,M=200010,inf=1e8;
inline int read()
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
int n,m,k,S,T;
int q[N],h[N],e[M],f[M],ne[M],cur[N],d[N],idx;
bool kill[600][600];
struct node
{
double x,y,r,t;
}lich[N],wisp[M],tree[N];
void add(int a,int b,int c)
{
e[idx]=b,f[idx]=c,ne[idx]=h[a],h[a]=idx++;
e[idx]=a,f[idx]=0,ne[idx]=h[b],h[b]=idx++;
}
bool bfs()
{
int tt=0,hh=0;
memset(d,-1,sizeof d);
q[0]=S,d[S]=0,cur[S]=h[S];
while(hh<=tt)
{
int t=q[hh++];
for(int i=h[t];~i;i=ne[i])
{
int ver=e[i];
if(d[ver]==-1&&f[i])
{
d[ver]=d[t]+1;
cur[ver]=h[ver];
if(ver==T) return true;
q[++tt]=ver;
}
}
}
return false;
}
int find(int u,int limit)
{
if(u==T) return limit;
int flow=0;
for(int i=cur[u];~i&&flow<limit;i=ne[i])
{
cur[u]=i;
int ver=e[i];
if(d[ver]==d[u]+1&&f[i])
{
int t=find(ver,min(limit-flow,f[i]));
if(!t) d[ver]=-1;
f[i]-=t,f[i^1]+=t,flow+=t;
}
}
return flow;
}
int dinic()
{
int ans=0,t;
while(bfs()) ans+=find(S,inf);
return ans;
}
bool check(int mid)
{
memset(h,-1,sizeof h);
S=0;idx=0;T=n+m+1;
for(int i=1;i<=n;i++)
{
add(S,i,mid/lich[i].t+1);//源点到巫妖建边,容量为可杀死的精灵数
}
for(int i=1;i<=m;i++)
{
add(i+n,T,1);//精灵到汇点建边,容量为 1
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(kill[i][j])
{
add(i,j+n,1);//巫妖到可杀死的精灵建边,容量为1
}
}
}
return dinic()>=m;
}
bool pd(node a,node b,node c,bool ok)
{
if(ok)//没树
{
if(a.r*a.r<(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)) return false;// 直接判断能不能攻击到
else true;
}
else//有树
{
if(a.r*a.r<(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)) return false; //先判断能不能攻击到
ll A=b.y-a.y,
B=a.x-b.x,
C=b.x*a.y-a.x*b.y;
if(c.r&&(A*c.x+B*c.y+C)*(A*c.x+B*c.y+C)>=(A*A+B*B)*c.r*c.r) return true;//如果能攻击到再判断树会不会挡住
else
{
int xi=(B*B*c.x-A*B*c.y-A*C),yi=(-A*B*c.x+A*A*c.y-B*C)/(A*A+B*B),temp=(A*A+B*B);//处理树到直线的垂点不在巫妖和精灵之间
if((a.y<yi&&yi<b.y)||(b.y<yi&&yi<a.y)) return false;
else return true;
}
}
}
int main()
{
n=read(),m=read(),k=read();
for(int i=1;i<=n;i++)
{
lich[i].x=read(),lich[i].y=read(),lich[i].r=read(),lich[i].t=read();
}
for(int i=1;i<=m;i++)
{
wisp[i].x=read(),wisp[i].y=read();
}
for(int i=1;i<=k;i++)
{
tree[i].x=read(),tree[i].y=read(),tree[i].r=read();
}
for(int i=1;i<=n;i++)//暴力枚举存储攻击关系
{
for(int j=1;j<=m;j++)
{
bool flag=true,ok=0;
int g;
if(k==0) g=0,ok=1;
else g=1;
for(;g<=k;g++)
{
if(!pd(lich[i],wisp[j],tree[g],ok))
{
flag=false;
break;
}
}
kill[i][j]=flag;
}
}
for(int i=1;i<=m;i++)//如果有精灵死不了就输出-1
{
bool flag=false;
for(int j=1;j<=n;j++)
{
if(kill[j][i]) flag=true;
}
if(!flag)
{
puts("-1");return 0;
}
}
int L=0,R=1e9,mid,res=-1;//二分最短的杀死所有精灵的时间
while(L<R)
{
mid=(L+R)>>1;
if(check(mid)) R=mid;
else L=mid+1;
}
printf("%d\n",R);
return 0;
}