Andrew Stankevich’s Contest #3解题报告 » ZOJ2361

ZOJ2361
ZOJ2361.cpp


#include <map>
#include <cmath>
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

const double EPS = 1e-8;

struct Point {
	double x, y;
};

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

bool operator==(const Point& lhs, const Point& rhs) {
	return fabs(lhs.x - rhs.x) < EPS && fabs(lhs.y - rhs.y) < EPS;
}

struct Line {
	Point a, b;
};

bool parallel(const Line& lhs, const Line& rhs) {
	return fabs((lhs.a.x - lhs.b.x) * (rhs.a.y - rhs.b.y) - (lhs.a.y - lhs.b.y) * (rhs.a.x - rhs.b.x)) < EPS;
}

Point intesection(const Line& lhs, const Line& rhs) {
	Point ret = lhs.a;
	double r =
		((lhs.a.x - rhs.a.x) * (rhs.a.y - rhs.b.y) - (lhs.a.y - rhs.a.y) * (rhs.a.x - rhs.b.x)) /
		((lhs.a.x - lhs.b.x) * (rhs.a.y - rhs.b.y) - (lhs.a.y - lhs.b.y) * (rhs.a.x - rhs.b.x));
	ret.x += (lhs.b.x - lhs.a.x) * r;
	ret.y += (lhs.b.y - lhs.a.y) * r;
	return ret;
}

struct Edge {
	double a;
	int p;
	bool m;
	Edge(double a, int p) : a(a), p(p), m(false) {
	}
};

struct CmpA {
	bool operator()(const Edge& lhs, const Edge& rhs) const {
		return lhs.a < rhs.a;
	}
};

int search(const vector<Edge>& v, double a) {
	int l, r, m;
	double d;
	d = a + M_PI - EPS;
	if (d >= M_PI) {
		d -= 2 * M_PI;
	}
	l = 0;
	r = v.size();
	while (l < r) {
		m = (l + r) / 2;
		if (v[m].a < d) {
			l = m + 1;
		} else {
			r = m;
		}
	}
	if (r == 0) {
		r = v.size() - 1;
	} else {
		--r;
	}
	d = v[r].a - a;
	if (d < 0) {
		d += 2 * M_PI;
	}
	if (d > M_PI - EPS) {
		return -1;
	} else {
		return r;
	}
}

const int MAXN = 81;

Line l[MAXN];
vector<Point> p[MAXN], vp;
map<Point, int> mp;
vector<Edge> e[MAXN * MAXN / 2];
vector<double> ans;

int main() {
	int re;
	int n, m, a, b, c;
	double s;

	scanf("%d", &re);
	for (int ri = 1; ri <= re; ++ri) {
		if (ri > 1) {
			puts("");
		}
		scanf("%d", &n);
		mp.clear();
		vp.clear();
		for (int i = 0; i < n; ++i) {
			scanf("%lf%lf%lf%lf", &l[i].a.x, &l[i].a.y, &l[i].b.x, &l[i].b.y);
			p[i].clear();
			for (int j = 0; j < i; ++j) {
				if (!parallel(l[i], l[j])) {
					Point pt = intesection(l[i], l[j]);
					mp[pt];
					p[i].push_back(pt);
					p[j].push_back(pt);
				}
			}
		}
		m = 0;
		for (map<Point, int>::iterator it = mp.begin(); it != mp.end(); ++it) {
			vp.push_back(it->first);
			it->second = m;
			e[m].clear();
			++m;
		}
		for (int i = 0; i < n; ++i) {
			if (p[i].size() < 2) {
				continue;
			}
			sort(p[i].begin(), p[i].end());
			p[i].erase(unique(p[i].begin(), p[i].end()), p[i].end());
			double ab = atan2(p[i].back().y - p[i].front().y, p[i].back().x - p[i].front().x);
			double ba = atan2(p[i].front().y - p[i].back().y, p[i].front().x - p[i].back().x);
			for (size_t j = 1; j < p[i].size(); ++j) {
				a = mp[p[i][j - 1]];
				b = mp[p[i][j]];
				e[a].push_back(Edge(ab, b));
				e[b].push_back(Edge(ba, a));
			}
		}
		for (int i = 0; i < m; ++i) {
			sort(e[i].begin(), e[i].end(), CmpA());
			/*
			fprintf(stderr, "* %.2lf %.2lf\n", vp[i].x, vp[i].y);
			for (size_t j = 0; j < e[i].size(); ++j) {
				fprintf(stderr, "> %.2lf %.2lf\n", vp[e[i][j].p].x, vp[e[i][j].p].y);
			}
			*/
		}
		ans.clear();
		for (int i = 0; i < m; ++i) {
			for (size_t j = 0; j < e[i].size(); ++j) {
				if (e[i][j].m) {
					continue;
				}
				a = i;
				b = j;
				s = vp[a].x * vp[e[a][b].p].y - vp[a].y * vp[e[a][b].p].x;
				e[a][b].m = true;
				// fprintf(stderr, "\n(%.2lf, %.2lf)\n", vp[a].x, vp[a].y);
				do {
					c = search(e[e[a][b].p], e[a][b].a);
					if (c == -1) {
						s = 0;
						// fprintf(stderr, "-1\n");
						break;
					}
					a = e[a][b].p;
					b = c;
					if (e[a][b].m) {
						s = 0;
						// fprintf(stderr, "mark\n");
						break;
					}
					s += vp[a].x * vp[e[a][b].p].y - vp[a].y * vp[e[a][b].p].x;
					e[a][b].m = true;
					// fprintf(stderr, "(%.2lf, %.2lf)\n", vp[a].x, vp[a].y);
				} while (e[a][b].p != i);
				// fprintf(stderr, "s=%.2lf\n", s);
				if (s > 2 * EPS) {
					// fprintf(stderr, "+ %.2lf\n", s);
					ans.push_back(s);
				}
			}
		}
		sort(ans.begin(), ans.end());	// Wrong answer on test 23 -_-b
		printf("%d\n", (int)ans.size());
		for (size_t i = 0; i < ans.size(); ++i) {
			printf("%.6lf\n", ans[i] / 2);
		}
	}

	return 0;
}

//Run ID  	Submit Time  	Judge Status  	Problem ID  	Language  	Run Time(ms)  	Run Memory(KB)  	User Name
//1807529 	2009-03-28 04:02:51 	Accepted 	2361 	C++ 	80 	788 	watashi@Zodiac
//1807528 	2009-03-28 04:02:28 	Accepted 	2361 	C++ 	80 	788 	watashi@Zodiac
Leave a Reply