【计算几何】【二分答案】【最大流】bzoj1822 [JSOI2010]Frozen Nova 冷冻波
用三角形面积什么的算算点到直线的距离之类……其实相切的情况是可行的……剩下的就跟某SDOI2015一样了。
#include<cstdio> #include<cmath> #include<algorithm> #include<cstring> #include<queue> using namespace std; #define N 201 #define EPS 0.000001 #define INF 2147483647 struct Point{int x,y;}jl[N]; typedef Point Vector; typedef double db; Vector operator - (Point a,Point b){return (Vector){a.x-b.x,a.y-b.y};} int Cross(Vector a,Vector b){return a.x*b.y-a.y*b.x;} int sqr(int x){return x*x;} db dis(Point a,Point b){return sqrt((db)(sqr(a.x-b.x)+sqr(a.y-b.y)));} struct WY{Point p; int r,t;}wy[N]; struct SHU{Point p; int r;}shu[N]; int Abs(int x){return x<0?(-x):x;} bool can[N][N]; int n,m,K; bool Can_Attack(WY a,Point b) { if((db)a.r-dis(a.p,b)<EPS) return 0; for(int i=1;i<=K;++i) if((db)Abs(Cross(a.p-b,shu[i].p-b))/dis(a.p,b)-(db)shu[i].r<-EPS) return 0; return 1; } bool Must_Be_Attacked(int x) { for(int i=1;i<=n;++i) if(can[i][x]) return 1; return 0; } queue<int>q; int nn,T,S; int v[2*N*(N+1)],en,first[N*2+3],next[2*N*(N+1)],cap[2*N*(N+1)]; int d[N*2+3],cur[N*2+3]; void AddEdge(int U,int V,int Cap) { v[en]=V; cap[en]=Cap; next[en]=first[U]; first[U]=en++; v[en]=U; cap[en]=0; next[en]=first[V]; first[V]=en++; } bool bfs() { memset(d,-1,sizeof(int)*(nn+1)); d[S]=0; q.push(S); while(!q.empty()) { int U=q.front(); q.pop(); for(int i=first[U];i!=-1;i=next[i]) if(cap[i]&&d[v[i]]==-1) { d[v[i]]=d[U]+1; q.push(v[i]); } } return d[T]!=-1; } int dfs(int U,int a) { if(U==T||(!a)) return a; int Flow=0,f; for(int i=first[U];i!=-1;i=next[i]) if(d[v[i]]==d[U]+1&&(f=dfs(v[i],min(a,cap[i])))) { cap[i]-=f; cap[i^1]+=f; Flow+=f; a-=f; if(!a) break; } if(!Flow) d[U]=-1; return Flow; } int MaxFlow() { int Flow=0,tmp; while(bfs()) { memcpy(cur,first,sizeof(int)*(nn+1)); while(tmp=dfs(S,INF)) Flow+=tmp; } return Flow; } bool check(int Lim) { memset(first,-1,sizeof(int)*(nn+1)); en=0; for(int i=1;i<=n;++i) AddEdge(S,1+i,(!Lim)?1:(Lim/wy[i].t+1)); for(int i=1;i<=m;++i) AddEdge(1+n+i,T,1); for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) if(can[i][j]) AddEdge(1+i,1+n+j,INF); return MaxFlow()==m?1:0; } int main() { scanf("%d%d%d",&n,&m,&K); for(int i=1;i<=n;++i) scanf("%d%d%d%d",&wy[i].p.x,&wy[i].p.y,&wy[i].r,&wy[i].t); for(int i=1;i<=m;++i) scanf("%d%d",&jl[i].x,&jl[i].y); for(int i=1;i<=K;++i) scanf("%d%d%d",&shu[i].p.x,&shu[i].p.y,&shu[i].r); for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) can[i][j]=Can_Attack(wy[i],jl[j]); for(int j=1;j<=m;++j) if(!Must_Be_Attacked(j)) {puts("-1"); return 0;} T=nn=n+m+2; S=1; int l=0,r=4000000; while(r>l) { int mid=(l+r>>1); if(check(mid)) r=mid; else l=mid+1; } printf("%d\n",l); return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。