﻿ P4048 【[JSOI2010]冷冻波】

### 题意：

WJJ喜欢“魔兽争霸”这个游戏。在游戏中，巫妖是一种强大的英雄，它的技能Frozen Nova每次可以杀死一个小精灵。我们认为，巫妖和小精灵都可以看成是平面上的点。

### sloution

``````#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cmath>
#include<cstring>
using namespace std;
const double eps = 1e-8;
const int inf = 1e7+10;
const int N = 2010;
int n,m,k,u,v,s,t,res,tot = 1;
bool used[N][N];
struct node
{
int to,net,w;
}e[100010];
struct point
{
int x,y;
point(){}
point(int a,int b){x = a, y = b;}
}c[N],p[N],tr[N];
typedef point Vector;
point operator + (point a,point b){return point(a.x+b.x,a.y+b.y);}
point operator - (point a,point b){return point(a.x-b.x,a.y-b.y);}
point operator * (point a,double k){return point(a.x*k,a.y*k);}
double Dot(point a,point b){return a.x*b.x+a.y*b.y;}
double Cro(point a,point b){return a.x*b.y-a.y*b.x;}
double dis(point a,point b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
double dis_PS(point p,point A,point B)
{
if(Dot(p-A,B-A) < 0) return dis(p,A);
if(Dot(p-B,A-B) < 0) return dis(p,B);
return abs(Cro(A-p,B-p))/dis(A,B);
}
{
e[++tot].to = y;
e[tot].w = w;
}
bool bfs()
{
queue<int> q;
for(int i = 0; i <= t; i++) dep[i] = 0;
q.push(s); dep[s] = 1;
while(!q.empty())
{
int x = q.front(); q.pop();
for(int i = head[x]; i; i = e[i].net)
{
int to = e[i].to;
if(e[i].w && !dep[to])
{
dep[to] = dep[x] + 1;
q.push(to);
if(to == t) return 1;
}
}
}
return 0;
}
int dinic(int x,int flow)
{
if(x == t || !flow) return flow;
int rest = flow, val = 0;
for(int i = head[x]; i && rest; i = e[i].net)
{
int to = e[i].to;
if(!e[i].w || dep[to] != dep[x] + 1) continue;
val = dinic(to,min(rest,e[i].w));
if(val == 0) dep[to] = 0;
e[i].w -= val; e[i^1].w += val; rest -= val;
}
return flow - rest;
}
bool judge(int mid)
{
s = 0, t = n+m+1, tot = 1, res = 0;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
}
}
int flow = 0;
while(bfs())
{
while(flow = dinic(s,inf)) res += flow;
}
return res >= m;
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i = 1; i <= n; i++) scanf("%d%d%d%d",&c[i].x,&c[i].y,&r[i],&tim[i]);
for(int i = 1; i <= m; i++) scanf("%d%d",&p[i].x,&p[i].y);
for(int i = 1; i <= k; i++) scanf("%d%d%d",&tr[i].x,&tr[i].y,&R[i]);
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
int flag = 0;
double tmp = dis(c[i],p[j]);
if(tmp > r[i]) continue;
for(int l = 1; l <= k; l++)
{
double tmp = dis_PS(tr[l],c[i],p[j]);
if(tmp <= R[l]) flag = 1;
}
if(flag == 0) used[i][j] = 1;
}
}
int L = 0, R = 500000, ans = -1;
while(L <= R)
{
int mid = (L + R)>>1;
if(judge(mid))
{
R = mid - 1;
ans = mid;
}
else L = mid + 1;
}
printf("%d
",ans);
return 0;
}
``````