题目
题目描述
WJJ喜欢“魔兽争霸”这个游戏。在游戏中，巫妖是一种强大的英雄，它的技能Frozen Nova每次可以杀死一个小精灵。我们认为，巫妖和小精灵都可以看成是平面上的点。
当巫妖和小精灵之间的直线距离不超过R，且巫妖看到小精灵的视线没有被树木阻挡（也就是说，巫妖和小精灵的连线与任何树木都没有公共点）的话，巫妖就可以瞬间杀灭一个小精灵。
在森林里有N个巫妖，每个巫妖释放Frozen Nova之后，都需要等待一段时间，才能再次施放。不同的巫妖有不同的等待时间和施法范围，但相同的是，每次施放都可以杀死一个小精灵。
现在巫妖的头目想知道，若从0时刻开始计算，至少需要花费多少时间，可以杀死所有的小精灵？
输入输出格式
输入格式：
输入文件第一行包含三个整数N、M、K(N,M,K<=200)，分别代表巫妖的数量、小精灵的数量和树木的数量。
接下来N行，每行包含四个整数x, y, r, t，分别代表了每个巫妖的坐标、攻击范围和施法间隔（单位为秒）。
再接下来M行，每行两个整数x, y，分别代表了每个小精灵的坐标。
再接下来K行，每行三个整数x, y, r，分别代表了每个树木的坐标。
输入数据中所有坐标范围绝对值不超过10000，半径和施法间隔不超过20000。
输出格式：
输出一行，为消灭所有小精灵的最短时间（以秒计算）。如果永远无法消灭所有的小精灵，则输出-1。
输入输出样例
输入样例#1：
2 3 1
-100 0 100 3
100 0 100 5
-100 -10
100 10
110 11
5 5 10
输出样例#1：
5
题解
其实这题除了计算几何有点恶心还是挺水的
首先一眼就看出这是二分流量最大流判断答案
然后处理巫妖和精灵的关系，由于树木有一个半径，所以要计算点到直线的距离
还有一点要注意，精灵可能在巫妖和树之间，所以计算前要判断一下精灵和树离巫妖的远近我的判断好像有漏洞但是水过了
判断出来就很水啦
二分时间，处理每个巫妖最多能发几次技能，注意$0s$时也能发一次
最大流开始打错了+数组开小了…RE WA了一片……
幸亏代码效率不错
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<cmath>
# include<queue>
using namespace std;
const int MAX=501,MAXN=1e5+1,inf=1e8;
struct p{
int x,y,dis;
}c[MAXN];
struct q{
double x,y,l,ti;
}s[MAX];
struct o{
double x,y;
}s1[MAX];
struct u{
double x,y,r;
}s2[MAX];
int n,m,t,k,num=2;
double maxn;
int d[MAX],h[MAX];
int kill[MAX][MAX];
bool use[MAX];
int read()
{
int x=0,f=1;
char ch=getchar();
for(;!isdigit(ch);f=(ch=='-')?-1:1,ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x*f;
}
bool bfs()
{
queue<int> qu;
qu.push(0);
memset(d,0,sizeof(d));
d[0]=1;
while(!qu.empty())
{
int tt=qu.front();
qu.pop();
for(int i=h[tt];i;i=c[i].x)
if(c[i].dis&&!d[c[i].y])
{
d[c[i].y]=d[tt]+1;
qu.push(c[i].y);
}
}
return d[t];
}
int dfs(int x,int dix)
{
if(x==t||!dix) return dix;
int sum=0;
for(int i=h[x];i;i=c[i].x)
if(d[c[i].y]==d[x]+1&&c[i].dis)
{
int dis=dfs(c[i].y,min(c[i].dis,dix));
if(dis)
{
sum+=dis;
dix-=dis;
c[i].dis-=dis;
c[i^1].dis+=dis;
if(!dix) break;
}
}
if(!sum) d[x]=-1;
return sum;
}
int dinic()
{
int tot=0;
while(bfs()) tot+=dfs(0,inf);
return tot;
}
void add(int x,int y,int dis)
{
c[num]=(p){h[y],x,0},h[y]=num++;
c[num]=(p){h[x],y,dis},h[x]=num++;
}
bool ss(int x,int y)
{
return (s[x].x-s1[y].x)*(s[x].x-s1[y].x)+(s[x].y-s1[y].y)*(s[x].y-s1[y].y)<=s[x].l*s[x].l;
}
double S(int x,int y)
{
if(s[x].x!=s1[y].x)
return (s[x].y-s1[y].y)/(s[x].x-s1[y].x);
}
bool sss(int x,int y,int z)
{
if(s[x].y<s1[y].y&&s2[z].y>=s[x].y&&s2[z].y-s2[z].r<=s1[y].y) return 1;
if(s[x].y>=s1[y].y&&s2[z].y<=s[x].y&&s2[z].y+s2[z].r>=s1[y].y) return 1;
return 0;
}
bool look(int mid)
{
num=2;
memset(h,0,sizeof(h));
for(int i=1;i<=m;++i)
add(i+n,t,1);
for(int i=1;i<=n;++i)
for(int j=1;j<=kill[i][0];++j)
add(i,kill[i][j]+n,1);
for(int i=1;i<=n;++i)
{
int tim=mid/s[i].ti+1;
add(0,i,tim);
}
if(dinic()==m) return 1;
return 0;
}
int main()
{
int sum=0;
n=read(),m=read(),k=read();
t=n+m+5;
for(int i=1;i<=n;++i)
{
s[i].x=read(),s[i].y=read(),s[i].l=read(),s[i].ti=read();
maxn=max(maxn,s[i].ti);
}
for(int i=1;i<=m;++i)
s1[i].x=read(),s1[i].y=read();
for(int i=1;i<=k;++i)
s2[i].x=read(),s2[i].y=read(),s2[i].r=read();
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
if(ss(i,j))
{
if(s[i].x==s1[j].x)
{
bool fl=0;
for(int l=1;l<=k;++l)
if(sss(i,j,l)&&s2[l].x+s2[l].r>=s[i].x&&s2[l].x-s2[l].r<=s[i].x)
{
fl=1;
break;
}
if(!fl)
{
kill[i][++kill[i][0]]=j;
if(!use[j]) use[j]=1,++sum;
}
}
else
{
double K=S(i,j),B=s[i].y-s[i].x*K;
bool fl=0;
for(int l=1;l<=k;++l)
if(sss(i,j,l))
{
double s=(K*s2[l].x-s2[l].y+B)/sqrt(K*K+1);
if(s<0) s=-s;
if(s<=s2[l].r)
{
fl=1;
break;
}
}
if(!fl)
{
kill[i][++kill[i][0]]=j;
if(!use[j]) use[j]=1,++sum;
}
}
}
}
if(sum!=m)
{
printf("-1");
return 0;
}
int l=0,r=maxn*m,ans=-1;
while(l<=r)
{
int mid=(l+r>>1);
if(look(mid)) ans=mid,r=mid-1;
else l=mid+1;
}
printf("%d",ans);
return 0;
}
