BZOJ1845 [Cqoi2005] 三角形面积并

比较基础的算几。当是hwd在wc的时候讲的东西拿来练练吧。（都过去多久了）

算几的板比较长。然后记得还有道半平面交精度题至今没过！？什么效率。

这题的思路比较简单。找出所有的关键x，分段。每段内都是一堆边不相交的梯形，那么答案=∑(▵x*∑中位线并的长度)。总时间复杂度到了O(n³)。不过n才100显然可过。至于n等于1000的题暂时不会啊。我太弱了。

然后这题也有神奇的精度误差，答案要-1e-7才能过。

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const double eps = 1e-7;
inline int sgn(double x) {
	return (x > eps) - (x < -eps);
}
inline double sqr(double x) {
	return x * x;
}

typedef struct geo_obj {
	double x, y;
	inline geo_obj() {}
	inline geo_obj(double x0, double y0) {
		x = x0, y = y0;
	}
	inline void read() {
		scanf("%lf%lf", &x, &y);
	}
} point, vect;
inline geo_obj operator +(const geo_obj& a, const geo_obj& b) {
	return geo_obj(a. x + b. x, a. y + b. y);
}
inline geo_obj operator -(const geo_obj& a, const geo_obj& b) {
	return geo_obj(a. x - b. x, a. y - b. y);
}
inline geo_obj operator *(const geo_obj& a, const double& b) {
	return geo_obj(a. x * b, a. y * b);
}
inline double operator *(const geo_obj& a, const geo_obj& b) {
	return a. x * b. y - a. y * b. x;
}
inline double operator &(const geo_obj& a, const geo_obj& b) {
	return a. x * b. x + a. y * b. y;
}
inline bool operator <(const geo_obj& a, const geo_obj& b) {
	return (a. x < b. x) || (a. x == b. x && a. y < b. y);
}

struct line {
	point p;
	vect v;
	inline line() {}
	inline line(const point& a, point& b) {
		p = a, v = b - a;
	}
};
struct triangle {
	point a[3];
	inline triangle() {}
	inline void read() {
		for (int i = 0; i < 3; ++ i)
			a[i]. read();
		if (sgn((a[1] - a[0]) * (a[2] - a[0])) < 0)
			swap(a[1], a[2]);
	}
};

typedef pair <double, int> ypr;

const int maxn = 109;
const int maxp = 90009;
const int ara[3] = {0, 1, 2}, arb[3] = {1, 2, 0};

int n, t, c;
triangle a[maxn];
double x[maxp], ans(0);
ypr y[maxp];

point lineCross(line a, line b) {
	vect w(b. p - a. p);
	double rat((w * a. v) / (a. v * b. v));
	return b. p + b. v * rat;
}

void addX(point a, point b, point c, point d) {
	if (!sgn((b - a) * (d - c)))
		return;
	point e(lineCross(line(a, b), line(c, d)));
	if (((a - e) & (b - e)) > 0 || ((c - e) & (d - e)) > 0)
		return;
	x[t ++] = e. x;
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
#endif

	scanf("%d", &n);
	for (int i = 0; i < n; ++ i)
		a[i]. read();
	t = 0;
	for (int i = 0; i < n; ++ i) {
		for (int j = 0; j < 3; ++ j)
			x[t ++] = a[i]. a[j]. x;
		for (int j = 0; j < i; ++ j)
			for (int k = 0; k < 3; ++ k)
				for (int l = 0; l < 3; ++ l)
					addX(a[i]. a[ara[k]], a[i]. a[arb[k]], a[j]. a[ara[l]], a[j]. a[arb[l]]);
	}
	sort(x, x + t);
	t = unique(x, x + t) - x;
	for (int i = 0; i < t - 1; ++ i) {
		double xm((x[i] + x[i + 1]) / 2.0);
		c = 0;
		for (int j = 0; j < n; ++ j)
			for (int k = 0; k < 3; ++ k) {
				point u(a[j]. a[ara[k]]), v(a[j]. a[arb[k]]);
				if ((xm - u. x) * (xm - v. x) < 0) {
					point w(u + (v - u) * ((xm - u. x) / (v. x - u. x)));
					y[c ++] = ypr(w. y, (u. x < v. x) ? 1 : -1);
				}
			}
		sort(y, y + c);
		int cnt(0);
		double len(0);
		for (int i = 0; i < c - 1; ++ i) {
			cnt += y[i]. second;
			if (cnt)
				len += (y[i + 1]. first - y[i]. first);
		}
		ans += len * (x[i + 1] - x[i]);
	}
	printf("%.2lf\n", ans - eps);
}