首页 > 代码库 > 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 }
BZOJ1043 [HAOI2008]下落的圆盘
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。