首页 > 代码库 > BZOJ 1043 HAOI 2008 下落的圆盘 计算几何
BZOJ 1043 HAOI 2008 下落的圆盘 计算几何
题目大意：给出一些圆盘，他们按照时间顺序相互覆盖，问最后的到的图形的可见圆周的周长是多少。
前言：円盘反对！让我们一起团结起来！赶走円盘！
思路：对于每一个圆盘，只要扫描在它后面出现的圆与它交的部分的并，总周长-相交的并就是剩下能看见的圆周的长度，然后累加到答案中。
对于两个圆的交，我们可以用一个有序数对(x,y)以弧度为单位来表示，这样所有的xy都在0~2π区间之内。求角度就利用余弦定理，见下图：
∠EAC就是我们要求的角。由于我们知道|AE|和|EC|分别是两个圆的半径，|AC|是圆心的距离，边都知道了就可以用余弦定理来求解任意一个角了。知道了这个角的大小，用向量(A->C)的极角加上∠EAC就是E点所代表的位置，减去∠EAC就是F点所代表的位置。这样就可以表示出两圆相交的区间了。
但是我们要保证所有的端点都在[0,2π]的区间之内，所以如果有加爆了或者减爆了的区间，要把他们分成两个区间。最后一步就是排序，然后求区间的并，计算可见的圆周长。
CODE：
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#define PI acos(-1.0)
#define MAX 1010
using namespace std;
struct Point{
double x,y;
Point(double _ = .0,double __ = .0):x(_),y(__) {}
Point operator -(const Point &a)const {
return Point(x - a.x,y - a.y);
}
void Read() {
scanf("%lf%lf",&x,&y);
}
};
struct Circle{
Point o;
double r;
void Read() {
scanf("%lf",&r);
o.Read();
}
}circle[MAX];
struct Interval{
double st,ed;
Interval(double _ = .0,double __ = .0):st(_),ed(__) {}
bool operator <(const Interval &a)const {
if(st == a.st) return ed < a.ed;
return st < a.st;
}
}interval[MAX];
int circles,cnt;
double ans;
inline double Calc(const Point &p1,const Point &p2)
{
return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}
inline void InsertInterval(const Circle &a,const Circle &b)
{
double dis = Calc(a.o,b.o);
if(dis > a.r + b.r) return ;
if(dis < a.r - b.r) return ;
if(dis < b.r - a.r) {
interval[++cnt] = Interval(.0,2.0 * PI);
return ;
}
Point u = b.o - a.o;
double alpha = atan2(u.y,u.x) + PI;
double detla = acos((a.r * a.r + dis * dis - b.r * b.r) / (2.0 * a.r * dis));
if(alpha - detla < 0) {
interval[++cnt] = Interval(alpha - detla + 2.0 * PI,2.0 * PI);
interval[++cnt] = Interval(0,alpha + detla);
}
else if(alpha + detla > 2.0 * PI) {
interval[++cnt] = Interval(alpha - detla,2.0 * PI);
interval[++cnt] = Interval(0,alpha + detla - 2.0 * PI);
}
else
interval[++cnt] = Interval(alpha - detla,alpha + detla);
}
int main()
{
cin >> circles;
for(int i = 1; i <= circles; ++i)
circle[i].Read();
for(int i = circles; i; --i) {
cnt = 0;
for(int j = i + 1; j <= circles; ++j)
InsertInterval(circle[i],circle[j]);
sort(interval + 1,interval + cnt + 1);
double start = .0,end = .0;
double length = .0;
for(int j = 1; j <= cnt; ++j)
if(interval[j].st > end)
length += end - start,start = interval[j].st,end = interval[j].ed;
else
end = max(end,interval[j].ed);
length += end - start;
length = PI * 2.0 - length;
ans += length * circle[i].r;
}
cout << fixed << setprecision(3) << ans << endl;
return 0;
}BZOJ 1043 HAOI 2008 下落的圆盘 计算几何
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。