BZOJ 1043 HAOI 2008 下落的圓盤 計算幾何

BZOJ 1043 HAOI 2008 下落的圓盤 計算幾何

題目大意：給出一些圓盤，他們按照時間順序相互覆蓋，問最後的到的圖形的可見圓周的周長是多少。

前言：円盤反對！讓我們一起團結起來！趕走円盤！

思路：對於每一個圓盤，只要掃描在它後面出現的圓與它交的部分的並，總周長-相交的並就是剩下能看見的圓周的長度，然後累加到答案中。

對於兩個圓的交，我們可以用一個有序數對(x,y)以弧度為單位來表示，這樣所有的xy都在0~2π區間之內。求角度就利用余弦定理，見下圖：

<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KIKHPRUFDvs3Kx87Sw8fSqsfztcS9x6Gj08nT2s7Sw8fWqrXA"AE|和|EC|分別是兩個圓的半徑，|AC|是圓心的距離，邊都知道了就可以用余弦定理來求解任意一個角了。知道了這個角的大小，用向量(A->C)的極角加上∠EAC就是E點所代表的位置，減去∠EAC就是F點所代表的位置。這樣就可以表示出兩圓相交的區間了。
但是我們要保證所有的端點都在[0,2π]的區間之內，所以如果有加爆了或者減爆了的區間，要把他們分成兩個區間。最後一步就是排序，然後求區間的並，計算可見的圓周長。
CODE：

#include 
#include 
#include 
#include 
#include 
#include 
#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;
}