[JSOI2010]冷冻波

题目描述

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。

思路

首先，考虑先预处理每个精灵能被多少巫妖攻击到。
对于每一对巫妖和精灵，巫妖能攻击到精灵，当且仅当该精灵在该巫妖的攻击范围以内，且巫妖和精灵的连线与任何树木都没有公共点。前者比较好判断，只需要看巫妖和精灵的直线距离是否\(<=\)巫妖的攻击范围即可。而对于后一种情况，我们需要知道：①树木的圆心到线段的距离是否\(dist\)\(>\)圆的半径\(r\)；②树木的圆心到线段的垂足\(c\)是否在线段上。因此，我们需要枚举巫妖\(i\)和精灵\(j\)，计算出\(i、j\)所连直线的方程，再枚举树木\(k\)，计算出树木圆心到线段的距离\(h\)。若\(h>r\)就不用管，否则的话看 \(i\)到垂足的距离 + \(j\)到垂足的距离 是否等于 \(dis(i,j)\)。若是，那么说明垂足在线段内（如图1），\(dist=r\)，否则在线段外（如图2），\(dist=min(dis(i，c)，dis(j，c))\)。


显然，预处理完了以后，若还有精灵不能被任何巫妖攻击到，那么一定永远无法被攻击到，直接输出\(-1\)。否则，所有精灵在时间充足的情况下一定会被全部攻击。这里有单调性，考虑二分时间。

但如何判断在给定的时间内能否攻击所有精灵呢？我们建立一个源点和一个汇点，将源点向所有的巫妖连一条边，边权为\(\frac{time}{wu[i].t}+1\)，表明每个巫妖可以攻击的次数为\((给定时间/一次所需时间)+1\)（第一次不花时间，所以要+1）。然后将每个巫妖向它所能攻击到的精灵连一条边权为\(1\)的边，表明只能攻击一次。最后，将每个精灵向汇点连一条边权为\(1\)的边。建完图之后跑最大流，若跑出来的结果\(==\)精灵个数，说明能攻击完所有精灵，否则不能。

照着上述的\(check\)方法二分，二分出来的结果便是最终的答案。

代码

#include<bits/stdc++.h>
#define MAXN 500
#define MAXM 1000000
#define eps 1e-7
#define INF 0x3f3f3f
#define int long long
using namespace std;
int n,m,k,x,y,r,t;
struct yao
{
    int x,y,r,t;
}wu[MAXN];
struct jl
{
    int x,y;
}jing[MAXN];
struct tree
{
    int x,y,r;
}tre[MAXN];
struct edge
{
    int to,nxt,w;
}ed[MAXM];
int head[MAXN],tot=0;
void add(int u,int v,int w)
{
    ed[++tot].to=v;
    ed[tot].w=w;
    ed[tot].nxt=head[u];
    head[u]=tot;
}
int ok[MAXN][MAXN<<1]={0};
double dis(int xa,int ya,int xb,int yb)
{
    return 1.0*sqrt((xa-xb+0.0)*(xa-xb+0.0)+(ya-yb+0.0)*(ya-yb+0.0));
}
struct line
{
    double a,b,c;
};
line get_line(int a,int b,int c,int d)
{
    return line{d-b,a-c,b*c-a*d};
}
double dis_pl(line l,int x,int y)
{
    return abs(l.a*x+l.b*y+l.c+0.0)/(sqrt(l.a*l.a+l.b*l.b+0.0));
}
double findis(line l,int x,int y,int xa,int ya,int xb,int yb)
{
    double c=dis_pl(l,x,y);
    if(sqrt(dis(x,y,xa,ya)*dis(x,y,xa,ya)-c*c)+sqrt(dis(x,y,xb,yb)*dis(x,y,xb,yb)-c*c)-dis(xa,ya,xb,yb)<eps)
    {
        return c;
    }
    else
    {
        return min(dis(x,y,xa,ya),dis(x,y,xb,yb));
    }
}
int ds[MAXN],pre[MAXN];
bool bfs()//分层
{
	memset(ds,-1,sizeof(ds));
	queue<int> q;
	ds[0]=1;
	q.push(0);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=head[u];i;i=ed[i].nxt)
		{
			int v=ed[i].to;
			if(ds[v]==-1&&ed[i].w>0)
			{
				ds[v]=ds[u]+1;
				q.push(v);
				if(v==n+m+1)return true;
			}
		}
	}
	return false;
}
int dfs(int x,int f)
{
	if(x==m+n+1)return f;
	for(int i=(pre[x]==-1?head[x]:pre[x]);i;i=ed[i].nxt)
	{
		int v=ed[i].to;
		pre[x]=i;
		if(ds[v]==ds[x]+1&&ed[i].w>0)
		{
			f=min(ed[i].w,f);
			int a=dfs(v,f);
			if(a!=0)
			{
				ed[i].w-=a;
				ed[i^1].w+=a;
				return a;
			}
		}
	}
	return 0;
}
long long max_flow()//每跑一次,把剩余网络重新分层
{
	long long f=0,a=0;
	while(bfs())
	{
		memset(pre,-1,sizeof(pre));
		a=dfs(0,INF);
		while(a!=0)
		{
			f+=a;
			a=dfs(0,INF);
		}
	}
	return f;
}
bool check(int tim)
{
    memset(ed,0,sizeof(ed));
    memset(head,0,sizeof(head));
    tot=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            if(ok[i][j+n])add(i,j+n,1),add(j+n,i,0);
    }
    for(int i=1;i<=n;i++)
		add(0,i,tim/wu[i].t+1),add(i,0,0);
    for(int i=1;i<=m;i++)
        add(i+n,n+m+1,1),add(n+m+1,i+n,0);
    int x=max_flow();
    return x==m;
}
int can[MAXN]={0};
signed main()
{
    scanf("%lld%lld%lld",&n,&m,&k);
    for(int i=1;i<=n;i++)
        scanf("%lld%lld%lld%lld",&wu[i].x,&wu[i].y,&wu[i].r,&wu[i].t);
    for(int i=1;i<=m;i++)
        scanf("%lld%lld",&jing[i].x,&jing[i].y);
    for(int i=1;i<=k;i++)
        scanf("%lld%lld%lld",&tre[i].x,&tre[i].y,&tre[i].r);
    for(int i=1;i<=m;i++)//预处理
    {
        for(int j=1;j<=n;j++)
        {
            if((dis(jing[i].x,jing[i].y,wu[j].x,wu[j].y)-wu[j].r)>eps)continue;
            line now=get_line(jing[i].x,jing[i].y,wu[j].x,wu[j].y);
            bool flag=0;
            for(int g=1;g<=k;g++)
            {
                if(tre[g].r-findis(now,tre[g].x,tre[g].y,jing[i].x,jing[i].y,wu[j].x,wu[j].y)>eps)flag=1;
            }
            if(!flag)ok[j][i+n]=1,can[i+n]=1;
        }
    }
    int l=0,r=20000000;
    for(int i=1;i<=m;i++)
    {
        if(!can[i+n])
        {
            printf("-1");
            return 0;
        }
    }
    while(l<r)
    {
        int mid=(l+r)>>1;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    printf("%lld",l);
    return 0;
}