首页 > 代码库 > BZOJ 1043 HAOI2008 下落的圆盘 计算几何
BZOJ 1043 HAOI2008 下落的圆盘 计算几何
题目大意:n个圆盘依次下落,求最终能看到的轮廓线面积
円盘反对!让我们一起团结起来!赶走円盘!
咳咳。很神的一道题 今天去看了题解和白书才搞出来……
首先我们倒着做 对于每个圆盘处理出在它之后落下的圆盘和它的覆盖区间 然后求一个区间并就能算出这个圆盘的可见弧长
然后就是相交部分怎么求的问题了
首先两个圆必须相交 然后作圆心1到圆心2的向量 用atan2求出极角 然后利用余弦定理求出两个交点和圆心连线的夹角即可 注意区间不在[0,2π]的部分要分割成另一个区间
处理起来其实不是很麻烦……都是技♂巧的问题
#include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define M 1010 #define PI 3.1415926536 using namespace std; struct point{ double x,y; }; struct circle{ point o; double r; }a[M]; int n; double ans; pair<double,double>intervals[M<<1];int tot; inline double Distance(const point &p1,const point &p2) { return sqrt( (p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y) ); } void Calculate(const circle o1,const circle o2,const double &dis) { double alpha=atan2(o2.o.y-o1.o.y,o2.o.x-o1.o.x)+PI; double delta=acos((o1.r*o1.r+dis*dis-o2.r*o2.r)/(2*o1.r*dis)); pair<double,double>temp(alpha-delta,alpha+delta); if(temp.first>=0&&temp.second<=2*PI) intervals[++tot]=temp; else if(temp.first<0) intervals[++tot]=make_pair(temp.first+2*PI,2*PI),intervals[++tot]=make_pair(0,temp.second); else intervals[++tot]=make_pair(temp.first,2*PI),intervals[++tot]=make_pair(0,temp.second-2*PI); } double Interval_Union() { int i; double re=0,st=-1,ed=-1; sort(intervals+1,intervals+tot+1); for(i=1;i<=tot;i++) { if(intervals[i].first>ed) re+=ed-st,st=intervals[i].first,ed=intervals[i].second; else ed=max(ed,intervals[i].second); } re+=ed-st; return 2*PI-re; } int main() { int i,j; cin>>n; for(i=n;i;i--) scanf("%lf%lf%lf",&a[i].r,&a[i].o.x,&a[i].o.y); for(i=1;i<=n;i++) { tot=0; for(j=1;j<i;j++) { double dis=Distance(a[i].o,a[j].o); if(a[j].r-a[i].r>dis) break; if(a[i].r+a[j].r>dis&&fabs(a[i].r-a[j].r)<dis) Calculate(a[i],a[j],dis); } if(j!=i) continue; ans+=Interval_Union()*a[i].r; } printf("%.3lf\n",ans); }
BZOJ 1043 HAOI2008 下落的圆盘 计算几何
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。