首页 > 代码库 > 【bzoj1043】[HAOI2008]下落的圆盘 计算几何
【bzoj1043】[HAOI2008]下落的圆盘 计算几何
题目描述
有n个圆盘从天而降，后面落下的可以盖住前面的。求最后形成的封闭区域的周长。看下面这副图, 所有的红色线条的总长度即为所求.
输入
第一行为1个整数n,N<=1000
接下来n行每行3个实数,ri,xi,yi,表示下落时第i个圆盘的半径和圆心坐标.
输出
最后的周长，保留三位小数
样例输入
2
1 0 0
1 1 0
样例输出
10.472
题解
计算几何
考虑从下到上的每一个圆，它被其它的圆覆盖了多少。即考虑它被覆盖了多少弧度。
考虑两个圆，如果相离则不覆盖，内含判断一下包含关系。
如果它们相交，则两个半径和圆心连线形成了一个三角形，使用余弦定理$a^2+b^2-c^2=2ab\cos C$可以求出交点与圆心连线的夹角，再用$atan2$求出极角，极角加减夹角即为覆盖弧度。
得到所有覆盖弧度范围后排序，求区间覆盖即可。
注意一下覆盖弧度范围跨越0和2π的处理。
#include <cmath>#include <cstdio>#include <cstring>#include <algorithm>#define N 1010#define squ(x) ((x) * (x))using namespace std;const double pi = acos(-1);struct data{ double pl , pr; bool operator<(const data &a)const {return pl < a.pl;}}a[N << 1];double x[N] , y[N] , r[N];int tot;int main(){ int n , i , j; double afa , beta , d , last , ans = 0; scanf("%d" , &n); for(i = 1 ; i <= n ; i ++ ) scanf("%lf%lf%lf" , &r[i] , &x[i] , &y[i]); for(i = 1 ; i <= n ; i ++ ) { ans += 2 * pi * r[i]; tot = 0; for(j = i + 1 ; j <= n ; j ++ ) { tot ++ , d = squ(x[i] - x[j]) + squ(y[i] - y[j]); if(squ(r[i] + r[j]) <= d) a[tot].pl = a[tot].pr = 0; else if(squ(r[i] - r[j]) >= d) { if(r[i] > r[j]) a[tot].pl = a[tot].pr = 0; else a[tot].pl = 0 , a[tot].pr = 2 * pi; } else { afa = acos((r[i] * r[i] + d - r[j] * r[j]) / (2 * r[i] * sqrt(d))); beta = atan2(y[j] - y[i] , x[j] - x[i]); if(beta < 0) beta += 2 * pi; a[tot].pl = beta - afa , a[tot].pr = beta + afa; if(a[tot].pl < 0) tot ++ , a[tot].pl = a[tot - 1].pl + 2 * pi , a[tot - 1].pl = 0 , a[tot].pr = 2 * pi; else if(a[tot].pr > 2 * pi) tot ++ , a[tot].pr = a[tot - 1].pr - 2 * pi , a[tot - 1].pr = 2 * pi , a[tot].pl = 0; } } sort(a + 1 , a + tot + 1); last = -1; for(j = 1 ; j <= tot ; j ++ ) { if(a[j].pr <= last) continue; if(a[j].pl > last) ans -= (a[j].pr - a[j].pl) * r[i]; else ans -= (a[j].pr - last) * r[i]; last = a[j].pr; } } printf("%.3lf\n" , ans); return 0;}
【bzoj1043】[HAOI2008]下落的圆盘 计算几何
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。