bzoj1822 [JSOI2010]Frozen Nova 冷冻波
Description
WJJ喜欢“魔兽争霸”这个游戏。在游戏中，巫妖是一种强大的英雄，它的技能Frozen Nova每次可以杀死一个小精灵。我们认为，巫妖和小精灵都可以看成是平面上的点。 当巫妖和小精灵之间的直线距离不超过R，且巫妖看到小精灵的视线没有被树木阻挡（也就是说，巫妖和小精灵的连线与任何树木都没有公共点）的话，巫妖就可以瞬间杀灭一个小精灵。 在森林里有N个巫妖，每个巫妖释放Frozen Nova之后，都需要等待一段时间，才能再次施放。不同的巫妖有不同的等待时间和施法范围，但相同的是，每次施放都可以杀死一个小精灵。 现在巫妖的头目想知道，若从0时刻开始计算，至少需要花费多少时间，可以杀死所有的小精灵？
Input
输入文件第一行包含三个整数N、M、K(N,M,K<=200)，分别代表巫妖的数量、小精灵的数量和树木的数量。 接下来N行，每行包含四个整数x, y, r, t，分别代表了每个巫妖的坐标、攻击范围和施法间隔（单位为秒）。 再接下来M行，每行两个整数x, y，分别代表了每个小精灵的坐标。 再接下来K行，每行三个整数x, y, r，分别代表了每个树木的坐标。 输入数据中所有坐标范围绝对值不超过10000，半径和施法间隔不超过20000。
Output
输出一行，为消灭所有小精灵的最短时间（以秒计算）。如果永远无法消灭所有的小精灵，则输出-1。
Sample Input
2 3 1
-100 0 100 3
100 0 100 5
-100 -10
100 10
110 11
5 5 10
Sample Output
5
HINTSource
JSOI2010第二轮Contest1
题目有点6.. 比较高级差点把树看成一个点..
做法：先二分一个答案，那么我们就知道每一个巫妖可以释放多少次【冷冻波】，然后就可用网络流判断这个答案是否满足题意..
问题就是判断线段与圆是否有交点.. 判断方法就是求线段到圆心的距离，如果这个距离小于半径那么线段和圆就有交点了啊啦啦啦..
code
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <cmath>
#define eps 1e-8
using namespace std;
const int Maxn = 210;
int _max ( int x, int y ){ return x > y ? x : y; }
int _min ( int x, int y ){ return x < y ? x : y; }
struct Point {double x, y;Point ( double x=0, double y=0 ) : x(x), y(y) {}
}xjl[Maxn];
typedef Point Vector;
int n, m, K;
struct Cricle {Point c;double r;
}tree[Maxn];
struct WY {Point p; double r; int t;
}wy[Maxn];
struct node {int x, y, next, c, opp;
}a[Maxn*Maxn*5]; int first[Maxn*2], len;
void ins ( int x, int y, int c ){len ++; int k1 = len;a[len].x = x; a[len].y = y; a[len].c = c;a[len].next = first[x]; first[x] = len;len ++; int k2 = len;a[len].x = y; a[len].y = x; a[len].c = 0;a[len].next = first[y]; first[y] = len;a[k1].opp = k2;a[k2].opp = k1;
}
bool v[Maxn][Maxn];
Vector operator + ( Vector A, Vector B ){ return Vector ( A.x+B.x, A.y+B.y ); }
Vector operator - ( Vector A, Vector B ){ return Vector ( A.x-B.x, A.y-B.y ); }
Vector operator * ( Vector A, double p ){ return Vector ( A.x*p, A.y*p ); }
Vector operator / ( Vector A, double p ){ return Vector ( A.x/p, A.y/p ); }
double _abs ( double x ){ return x < 0 ? -x : x; }
int zero ( double x ){ return _abs (x) < eps ? 1 : 0; }
int dcmp ( double x ){if ( zero (x) == 1 ) return 0;return x < 0 ? -1 : 1;
}
bool operator == ( const Point &a, const Point &b ){return zero (a.x-b.x) && zero (a.y-b.y);
}
double Dot ( Vector A, Vector B ){ return A.x*B.x + A.y*B.y; }
double Length ( Vector A ){ return sqrt ( Dot ( A, A ) ); }
double Cross ( Vector A, Vector B ){ return A.x*B.y - A.y*B.x; }
double DistanceToSegment ( Point P, Point A, Point B ){if ( A == B ) return Length (P-A);Vector v1 = B-A, v2 = P-A, v3 = P-B;if ( dcmp ( Dot ( v1, v2 ) ) < 0 ) return Length (v2);else if ( dcmp ( Dot ( v1, v3 ) ) > 0 ) return Length (v3);else return _abs ( Cross ( v1, v2 ) ) / Length (v1);
}
int st, ed, h[Maxn*2];
bool bfs (){queue <int> q;memset ( h, -1, sizeof (h) );h[st] = 0; q.push (st);while ( !q.empty () ){int x = q.front (); q.pop ();for ( int k = first[x]; k; k = a[k].next ){int y = a[k].y;if ( h[y] == -1 && a[k].c > 0 ){h[y] = h[x]+1;q.push (y);}}}return h[ed] > 0;
}
int dfs ( int x, int flow ){if ( x == ed ) return flow;int delta = 0;for ( int k = first[x]; k; k = a[k].next ){int y = a[k].y;if ( h[y] == h[x]+1 && a[k].c > 0 && flow-delta > 0 ){int minf = dfs ( y, _min ( a[k].c, flow-delta ) );delta += minf;a[k].c -= minf;a[a[k].opp].c += minf;}}if ( delta == 0 ) h[x] = -1;return delta;
}
int main (){int i, j, k;scanf ( "%d%d%d", &n, &m, &K );int mx = 0;for ( i = 1; i <= n; i ++ ){scanf ( "%lf%lf%lf%d", &wy[i].p.x, &wy[i].p.y, &wy[i].r, &wy[i].t );mx = _max ( mx, wy[i].t );}for ( i = 1; i <= m; i ++ ){scanf ( "%lf%lf", &xjl[i].x, &xjl[i].y );}for ( i = 1; i <= K; i ++ ){scanf ( "%lf%lf%lf", &tree[i].c.x, &tree[i].c.y, &tree[i].r );}memset ( v, false, sizeof (v) );for ( i = 1; i <= n; i ++ ){for ( j = 1; j <= m; j ++ ){int bk = true;if ( Length (wy[i].p-xjl[j]) > wy[i].r ){ v[i][j] = false; continue; }for ( k = 1; k <= K && bk == true; k ++ ){if ( DistanceToSegment ( tree[k].c, wy[i].p, xjl[j] ) <= tree[k].r ){bk = false;}}v[i][j] = bk;}}int l = 0, r = mx*m;int ret = -1;while ( l <= r ){int mid = ( l + r ) >> 1;st = 0; ed = n+m+1;len = 0; memset ( first, 0, sizeof (first) );for ( i = 1; i <= n; i ++ ) ins ( st, i, mid/wy[i].t+1 );for ( i = 1; i <= m; i ++ ) ins ( i+n, ed, 1 );for ( i = 1; i <= n; i ++ ){for ( j = 1; j <= m; j ++ ){if ( v[i][j] == true ) ins ( i, j+n, 1 );}}int ans = 0, delta;while ( bfs () ){while ( delta = dfs ( st, 0x7ffffff ) ) ans += delta;}if ( ans == m ){ ret = mid; r = mid-1; }else l = mid+1;}printf ( "%d\n", ret );return 0;
}