BZOJ1822:[JSOI2010]Frozen Nova 冷冻波 二分+计算几何+网络流

思路:

一眼网络流,套一个二分就行了.

关键是如何判断巫妖和精灵之间能否有圆阻挡.

一开始我是进行了复杂的判断:如果线段平行于x轴或者平行于y轴直接特判;

否则求出圆心到直线的距离,如果距离不超过半径,则用一个简单的公式求出圆心到直线最近点的横坐标,利用这个横坐标与线段两个端点的横坐标比较,得出结果.

可是数据跟我想的根本不是一回事啊啊啊!

根本只需要判断距离啊啊啊!!而且相切的情况不算相交啊啊啊!!

什么坑爹数据,我是领教到了.

#include<cstdio>
#include<cstring>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long LL;

#define INF 0x3f3f3f3f

#define N 210
#define M 210
#define P 210

struct MaxflowSolver{
	static const int V=410;
	static const int E=100010;
	int head[V],next[E],end[E],flow[E],ind,d[V];
	inline void reset(){ind=0,memset(head,-1,sizeof head);}
	inline void addedge(int a,int b,int f){int q=ind++;end[q]=b,next[q]=head[a],head[a]=q,flow[q]=f;}
	inline void make(int a,int b,int f){addedge(a,b,f),addedge(b,a,0);}
	inline bool bfs(int S,int T){
		static int q[V];int fr=0,ta=0;
		memset(d,-1,sizeof d),d[S]=0,q[ta++]=S;
		while(fr^ta){
			int i=q[fr++];for(int j=head[i];j!=-1;j=next[j])if(flow[j]&&d[end[j]]==-1)d[end[j]]=d[i]+1,q[ta++]=end[j];
		}return d[T]!=-1;
	}
	inline int dinic(int p,int T,int Maxflow){
		if(p==T)return Maxflow;
		int last=Maxflow;
		for(int j=head[p];j!=-1;j=next[j])if(flow[j]&&d[end[j]]==d[p]+1){
			int to=dinic(end[j],T,last>flow[j]?flow[j]:last);
			if(to){flow[j]-=to,flow[j^1]+=to;if(!(last-=to))return Maxflow;}
		}d[p]=-1;return Maxflow-last;
	}
	inline int Maxflow(int S,int T){
		int res=0;while(bfs(S,T))res+=dinic(S,T,INF);return res;
	}
}Stg;
int x1[N],y1[N],x2[M],y2[M],lim[N],cd[N],ox[P],oy[P],r[P];

int G[N][M];

inline int sqr(int x){return x*x;}



int main(){
	int n,m,p;scanf("%d%d%d",&n,&m,&p);register int i,j,k;
	for(i=1;i<=n;++i)scanf("%d%d%d%d",&x1[i],&y1[i],&lim[i],&cd[i]);
	for(i=1;i<=m;++i)scanf("%d%d",&x2[i],&y2[i]);
	for(i=1;i<=p;++i)scanf("%d%d%d",&ox[i],&oy[i],&r[i]);
	
	int a,b,c;
	for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(sqr(x1[i]-x2[j])+sqr(y1[i]-y2[j])<=sqr(lim[i])){
		bool ok=1;
		for(k=1;k<=p&&ok;++k){
			a=y1[i]-y2[j],b=x2[j]-x1[i],c=(x1[i]-x2[j])*y1[i]-(y1[i]-y2[j])*x1[i];
			if((LL)(a*ox[k]+b*oy[k]+c)*(a*ox[k]+b*oy[k]+c)<(LL)r[k]*r[k]*(a*a+b*b))ok=0;
		}
		if(ok)G[i][j]=1;
	}
	
	int L=0,R=1<<30,mid;
	while(L<R){
		mid=(L+R)>>1;
		Stg.reset();
		for(i=1;i<=n;++i)Stg.make(0,i,mid/cd[i]+1);
		for(i=1;i<=m;++i)Stg.make(n+i,n+m+1,1);
		for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(G[i][j])Stg.make(i,n+j,1);
		if(Stg.Maxflow(0,n+m+1)==m)R=mid;else L=mid+1;
	}
	
	if(L==1<<30)puts("-1");else printf("%d",L);
	return 0;
}