Andrew Stankevich’s Contest #5解题报告 » ZOJ2589

ZOJ2589
ZOJ2589.cpp


/*
Euler characteristic

http://en.wikipedia.org/wiki/Euler_characteristic

χ=V-E+F
*/

#include <set>
#include <cmath>
#include <cstdio>
#include <algorithm>

using namespace std;

const double eps = 1e-8;

struct Point {
	double x, y;
};

inline bool operator<(const Point& lhs, const Point& rhs) {
	if (fabs(lhs.x - rhs.x) > 1e-8) {
		return lhs.x < rhs.x;
	} else if (fabs(lhs.y - rhs.y) > 1e-8) {
		return lhs.y < rhs.y;
	} else {
		return false;
	}
}

inline double sqr(double x) {
	return x * x;
}

inline double dis(const Point& lhs, const Point& rhs) {
	return hypot(lhs.x - rhs.x, lhs.y - rhs.y);
}

// |dx'|   |dx|   |cosa -sina|
// |   | = |  | * |          |
// |dy'|   |dy|   |sina  cosa|

bool intersection(const Point& o1, double r1, const Point& o2, double r2, Point& p1, Point& p2) {
	double d = dis(o1, o2);
	if (d < fabs(r1 - r2) - eps || d > r1 + r2 + eps) {
		return false;
	}
	double cosa = (sqr(r1) + sqr(d) - sqr(r2)) / (2 * r1 * d);
	double sina = sqrt(max(0., 1. - sqr(cosa)));
	p1 = p2 = o1;
	p1.x += r1 / d * ((o2.x - o1.x) * cosa + (o2.y - o1.y) * -sina);
	p1.y += r1 / d * ((o2.x - o1.x) * sina + (o2.y - o1.y) * cosa);
	p2.x += r1 / d * ((o2.x - o1.x) * cosa + (o2.y - o1.y) * sina);
	p2.y += r1 / d * ((o2.x - o1.x) * -sina + (o2.y - o1.y) * cosa);
	return true;
}

int main() {
	int re, n, f;
	bool w[64][64], v[64];
	double r[64];
	Point a, b, o[64];
	set<Point> pp, p[64];

	scanf("%d", &re);
	for (int ri = 1; ri <= re; ++ri) {
		scanf("%d", &n);
		pp.clear();
		for (int i = 0; i < n; ++i) {
			scanf("%lf%lf%lf", &o[i].x, &o[i].y, &r[i]);
			p[i].clear();
			v[i] = false;
			w[i][i] = true;
			for (int j = 0; j < i; ++j) {
				if (intersection(o[i], r[i], o[j], r[j], a, b)) {
					pp.insert(a); p[i].insert(a); p[j].insert(a);
					pp.insert(b); p[i].insert(b); p[j].insert(b);
					w[i][j] = w[j][i] = true;
				} else {
					w[i][j] = w[j][i] = false;
				}
			}
		}
		for (int k = 0; k < n; ++k) {
			for (int i = 0; i < n; ++i) {
				for (int j = 0; j < n; ++j) {
					w[i][j] |= w[i][k] & w[k][j];
				}
			}
		}
		f = 1;
		for (int i = 0; i < n; ++i) {
			f += p[i].size();
			if (!v[i]) {
				++f;
				for (int j = 0; j < n; ++j) {
					v[j] |= w[i][j];
				}
			}
		}
		f -= pp.size();
		printf("%d\n", f);
	}

	return 0;
}

//Run ID  	Submit Time  	Judge Status  	Problem ID  	Language  	Run Time(ms)  	Run Memory(KB)  	User Name
//1832251 	2009-04-13 16:42:17 	Accepted 	2589 	C++ 	20 	440 	watashi@Zodiac
Leave a Reply