首页 > 代码库 > BZOJ1822 Frozen Nova 冷冻波

BZOJ1822 Frozen Nova 冷冻波

1822: [JSOI2010]Frozen Nova 冷冻波

Time Limit: 10 Sec  Memory Limit: 64 MB

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

Source

JSOI2010第二轮Contest1


题解

网络流 + 二分答案 + 计算几何

计算几何用点积和叉积计算点到线段距离,二分所需时间,网络流验证是否可行

大水题,数据有点坑qwq

代码

技术分享
  1 #include<bits/stdc++.h>  2 using namespace std;  3 template <class _T> inline void read(_T &_x) {  4     int _t; bool flag = false;  5     while ((_t = getchar()) != - && (_t < 0 || _t > 9)) ;  6     if (_t == -) _t = getchar(), flag = true; _x = _t - 0;  7     while ((_t = getchar()) >= 0 && _t <= 9) _x = _x * 10 + _t - 0;  8     if (flag) _x = -_x;  9 } 10 typedef long long LL; 11 const int maxn = 1010; 12 const int maxm = 100010; 13 const double eps = 1e-8; 14 inline int sign(double val) {return val < -eps ? -1 : val > eps; } 15 struct Point { 16     double x, y; 17     Point (double a = 0, double b = 0):x(a), y(b) {} 18 }A[maxn], B[maxn], C[maxn]; 19 double rA[maxn], rC[maxn]; 20 double dot(Point a, Point b, Point c) { 21     return (b.x - a.x) * (c.x - a.x) + (b.y - a.y) * (c.y - a.y); 22 } 23 double cross(Point a, Point b, Point c) { 24     return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y); 25 } 26 double dist(Point a, Point b) { 27     return hypot(a.x - b.x, a.y - b.y); 28 } 29 double ldis(Point a, Point b, Point c) { 30     if (dot(c, a, b) > 0) return min(dist(a, c), dist(b, c)); 31     return fabs(cross(a, b, c) / dist(a, b)); 32 } 33 bool check(Point a, Point b, Point c, int pc) { 34     double dis = dist(a, b), r = dot(a, b, c) / dis; 35     if (r < 0 || r > dis) return true; 36     return sign(fabs(cross(a, b, c) / r) - rC[pc]) > 0; 37 } 38 struct Edge { 39     int v, flow, nxt; 40     Edge () {} 41     Edge (int a, int b, int c):v(a), flow(b), nxt(c) {} 42 }e[maxm]; 43 int n, m, k, t[maxn], sink; 44 int fir[maxn], tag[maxn], cur[maxn], ecnt; 45 bool can[maxn][maxn]; 46 inline void addedge (int a, int b, int c) { 47     e[++ecnt] = Edge (b, c, fir[a]), fir[a] = ecnt; 48     e[++ecnt] = Edge (a, 0, fir[b]), fir[b] = ecnt; 49 } 50 inline bool bfs() { 51     memset(tag, 0, sizeof (int) * (sink + 1)); 52     queue<int> q; q.push(0), tag[0] = 1; 53     while (!q.empty()) { 54         int now = q.front(); q.pop(); 55         for (int u = fir[now]; u; u = e[u].nxt) { 56             if (e[u].flow && !tag[e[u].v]) { 57                 tag[e[u].v] = tag[now] + 1; 58                 q.push(e[u].v); 59             } 60         } 61     } 62     return tag[sink] != 0; 63 } 64 int dfs(int now, int flow) { 65     if (now == sink) return flow; 66     int usd = 0; 67     for (int &u = cur[now]; u; u = e[u].nxt) { 68         if (e[u].flow && tag[e[u].v] > tag[now]) { 69             int ret = dfs(e[u].v, min(e[u].flow, flow - usd)); 70             if (ret) { 71                 e[u].flow -= ret; 72                 e[u ^ 1].flow += ret; 73                 usd += ret; 74                 if (usd == flow) return flow; 75             } 76         } 77     } 78     return usd; 79 } 80 inline int dinic() { 81     int flow = 0; 82     while (bfs()) { 83         for (int i = 0; i <= sink; ++i) cur[i] = fir[i]; 84         flow += dfs(0, m); 85     } 86     return flow; 87 } 88 bool check(int tim) { 89     memset(fir, 0, sizeof (int) * (sink + 1)); 90     ecnt = 1; 91     for (int i = 1; i <= n; ++i) { 92         addedge(0, i, tim / t[i] + 1); 93         for (int j = 1; j <= m; ++j) if (can[i][j]) { 94             addedge(i, n + j, 1); 95         } 96     } 97     for (int i = 1; i <= m; ++i) addedge(n + i, sink, 1); 98     return dinic() >= m; 99 }100 int main() {101     //freopen(".in", "r", stdin);102     //freopen(".out", "w", stdout);103     read(n), read(m), read(k);104     for (int i = 1; i <= n; ++i) {105         scanf("%lf%lf%lf%d", &A[i].x, &A[i].y, &rA[i], &t[i]);106     }107     for (int i = 1; i <= m; ++i) {108         scanf("%lf%lf", &B[i].x, &B[i].y);109     }110     for (int i = 1; i <= k; ++i) {111         scanf("%lf%lf%lf", &C[i].x, &C[i].y, &rC[i]);112     }113     for (int i = 1; i <= n; ++i) {114         for (int j = 1; j <= m; ++j) {115             bool flag = true;116             double dis = dist(A[i], B[j]);117             if (dis > rA[i]) continue;118             for (int x = 1; x <= k; ++x) {119                 if (ldis(A[i], B[j], C[x]) < rC[x]) {120                     flag = false;121                     break;122                 }123             }124             if (flag) can[i][j] = true;125         }126     }127     for (int i = 1; i <= m; ++i) {128         bool flag = false;129         for (int j = 1; j <= n; ++j) if (can[j][i]) {130             flag = true; break;131         }132         if (!flag) {133             puts("-1");134             return 0;135         }136     }137     sink = n + m + 1;138     int l = 0, r = 20000 * m, mid;139     while (l < r) {140         if (check(mid = (l + r) >> 1)) r = mid;141         else l = mid + 1;142     }143     cout << l << endl;144     return 0;145 }
View Code

 

BZOJ1822 Frozen Nova 冷冻波