2246.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2246 on 2006-08-19 at 16:49:26 */ 
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 128;
const double eps = 1e-5;

class Zone {
public:
	double a;
	int ent, o;
	Zone(double ca, int ce, int co) : a(ca), ent(ce), o(co) {}
	bool operator <(const Zone& z) const { return a+eps < z.a; }
};

class Disc {
private:
	double x, y, r;
	vector<Zone> zone;
	void insert(double la, double ra, int k) { zone.push_back(Zone(la, 1, k)); zone.push_back(Zone(ra, 0, k)); }
public:
	void make();
	void overlap(const Disc&);
	double perimeter();
};
void Disc::make() {
	zone.clear();
	scanf("%lf %lf %lf", &r, &x, &y);
}
void Disc::overlap(const Disc& d) {
	double rd = hypot(x-d.x, y-d.y);
	if(rd+eps > r+d.r) return;
	else if(rd < fabs(r-d.r)+eps) {
		if(r < d.r+eps) insert(-M_PI, M_PI, zone.size()/2);
		return;
	}
	double ba = atan2(d.y-y, d.x-x), da = acos((rd*rd+r*r-d.r*d.r)/(2*rd*r));
	double la = ba-da, ra = ba+da;
	while(la < -M_PI) la += 2*M_PI;
	while(ra > M_PI) ra -= 2*M_PI;
	insert(la, ra, zone.size()/2);
}
double Disc::perimeter() {
	if(zone.size() == 0) return 2*M_PI*r;
	sort(zone.begin(), zone.end());
	bool m[N] = { false };
	double tl = 0;
	int on = 0, b, n = zone.size();
	for(b = 0; !zone[b].ent; b++);
	for(int i = b, j = 2*n; j > 0; i = (i+1)%n, j--) {
		if(zone[i].ent) { on++; m[zone[i].o] = true; }
		else if(m[zone[i].o]) { on--; m[zone[i].o] = false; }
		if(on == 0 && j <= n) {
			tl += zone[(i+1)%n].a-zone[i].a;
			if(i == n-1) tl += 2*M_PI;
		}
	}
	return tl*r;
}

int main()
{
	int n;
	Disc d[N];
	
	while(scanf("%d", &n) != EOF) {
		for(int i = 0; i < n; i++) d[i].make();
		for(int i = 0; i < n; i++)
			for(int j = i+1; j < n; j++) d[i].overlap(d[j]);
		double r = 0;
		for(int i = 0; i < n; i++) r += d[i].perimeter();
		printf("%.3lf\n", r);
	}
	
	return 0;
}