BZOJ1845 [Cqoi2005] 三角形面积并

			    <div class="post_brief"><p>
比较基础的算几。当是hwd在wc的时候讲的东西拿来练练吧。（都过去多久了）</p>

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

这题的思路比较简单。找出所有的关键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", &amp;n);
for (int i = 0; i &lt; n; ++ i)
	a[i]. read();
t = 0;
for (int i = 0; i &lt; n; ++ i) {
	for (int j = 0; j &lt; 3; ++ j)
		x[t ++] = a[i]. a[j]. x;
	for (int j = 0; j &lt; i; ++ j)
		for (int k = 0; k &lt; 3; ++ k)
			for (int l = 0; l &lt; 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 &lt; t - 1; ++ i) {
	double xm((x[i] + x[i + 1]) / 2.0);
	c = 0;
	for (int j = 0; j &lt; n; ++ j)
		for (int k = 0; k &lt; 3; ++ k) {
			point u(a[j]. a[ara[k]]), v(a[j]. a[arb[k]]);
			if ((xm - u. x) * (xm - v. x) &lt; 0) {
				point w(u + (v - u) * ((xm - u. x) / (v. x - u. x)));
				y[c ++] = ypr(w. y, (u. x &lt; v. x) ? 1 : -1);
			}
		}
	sort(y, y + c);
	int cnt(0);
	double len(0);
	for (int i = 0; i &lt; 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);

}

Comments