首页 > 代码库 > BZOJ1043 [HAOI2008]下落的圆盘

BZOJ1043 [HAOI2008]下落的圆盘

倒过来做,然后就变成了线段覆盖问题了。

线段覆盖就是贪心即可。。。

但是好烦好烦= =,需要耐心和几何基础2333

 

 1 /************************************************************** 2     Problem: 1043 3     User: rausen 4     Language: C++ 5     Result: Accepted 6     Time:240 ms 7     Memory:872 kb 8 ****************************************************************/ 9  10 #include <cstdio>11 #include <cmath>12 #include <algorithm>13  14 using namespace std;15 typedef double lf;16 typedef pair <lf, lf> Pair;17 const lf pi = 3.1415926536;18 const int N = 1005;19  20 struct point {21     lf x, y;22 };23 typedef point P;24  25 struct circle {26     P o;27     lf r;28 }a[N];29 typedef circle C;30  31 int n, tot;32 lf ans;33 Pair inter[N << 1];34  35 inline lf Sqr(lf x) {36     return x * x;37 }38  39 inline lf dist(const P & a, const P &b) {40     return sqrt(Sqr(a.x - b.x) + Sqr(a.y - b.y));41 }42  43 inline lf K(const P &a, const P &b) {44     return atan2(a.y - b.y, a.x - b.x);45 }46  47 void Calc (C O1, C O2, lf &dis) {48     lf alpha = K(O1.o, O2.o) + pi,49     delta = acos((Sqr(O1.r) + Sqr(dis) - Sqr(O2.r)) / (2 * O1.r * dis));50     Pair tmp = make_pair(alpha - delta, alpha + delta);51     if (tmp.first >= 0 && tmp.second <= 2 * pi)52         inter[++tot] = tmp; 53     else if (tmp.first < 0)54         inter[++tot] = make_pair(tmp.first + 2 * pi, 2 * pi),55         inter[++tot] = make_pair(0, tmp.second);56     else57         inter[++tot] = make_pair(tmp.first, 2 * pi),58         inter[++tot] = make_pair(0, tmp.second - 2 * pi);59 }60  61 lf Union() {62     int i;63     lf res = 0, st = -1, ed = -1;64     sort(inter + 1, inter + tot + 1);65     for (i = 1; i <= tot; ++i) {66         if (inter[i].first > ed) {67             res += ed - st;68             st = inter[i].first, ed = inter[i].second;69         } else70             ed = max(ed, inter[i].second);71     }72     res += ed - st;73     return 2 * pi - res;74 }75  76 int main() {77     int i, j;78     lf dis;79     scanf("%d\n", &n);80     for (i = n; i; --i)81         scanf("%lf%lf%lf", &a[i].r, &a[i].o.x, &a[i].o.y);82     for (i = 1; i <= n; ++i) {83         tot = 0;84         for (j = 1; j < i; ++j) {85             dis = dist(a[i].o, a[j].o);86             if (a[j].r - a[i].r > dis) break;87             if (a[i].r + a[j].r > dis && fabs(a[i].r - a[j].r) < dis)88                 Calc(a[i], a[j], dis);89         }90         if (j == i)91             ans += Union() * a[i].r;92     }93     printf("%.3lf\n", ans);94     return 0;95 }
View Code

 

BZOJ1043 [HAOI2008]下落的圆盘