交的是POJ3335、1474、1279的模板，应该没有错了……
第1次WA后，在网上搜，结果以为将zero = 1e-8改成zero = 1e-10就过了，可是还是WA……
第2次WA后，以为顶点顺序可能是逆时针，有改了改，还是WA……
第3次WA后，没信心了，把第1次交的代码随便看看，乱改改，再试试，就AC了……
无语……
最后一次的代码如下，纪念一下：
#include<cstdio>

using namespace std;

const int maxn = 3005;
const double zero = 1e-8;

struct Tpoint{
	double x, y;
};

struct Tpgn{
	int n; Tpoint ps[maxn];
} Pts, Ret;

int T; double ans;

void init()
{
	scanf("%d", &Pts.n);
	for (int i = 0; i < Pts.n; i++) scanf("%lf%lf", &Pts.ps[i].x, &Pts.ps[i].y);
	Pts.ps[Pts.n] = Pts.ps[0];
}

inline double Fabs(double x)
{
	return x > 0 ? x : -x;
}

inline double cross(Tpoint p0, Tpoint p1, Tpoint p2)
{
	return (p1.x - p0.x) * (p2.y - p0.y) - (p1.y - p0.y) * (p2.x - p0.x);
}

inline bool same(Tpoint p0, Tpoint p1)
{
	return Fabs(p1.x - p0.x) < zero && Fabs(p1.y - p0.y) < zero;
}

inline Tpoint get_point(double a1, double b1, double c1, double a2, double b2, double c2)
{
	Tpoint ret; ret.y = (c2 * a1 - c1 * a2) / (b1 * a2 - b2 * a1);
	if (Fabs(a2) < zero) ret.x = -(b1 * ret.y + c1) / a1;
		else ret.x = -(b2 * ret.y + c2) / a2;
	return ret;
}

inline void get_line(Tpoint p0, Tpoint p1, double &a, double &b, double &c)
{
	a = p1.y - p0.y; b = p0.x - p1.x;
	c = -(a * p0.x + b * p0.y);
}

Tpgn calc(Tpoint p0, Tpoint p1, Tpgn Now)
{
	Tpgn ret; int i, j; double t1, t2; 
	double a1, b1, c1, a2, b2, c2; Tpoint tmp;
	get_line(p0, p1, a1, b1, c1);
	ret.n = 0;
	for (i = 0; i < Now.n; i++){
		j = i + 1;
		t1 = cross(p0, p1, Now.ps[i]);
		t2 = cross(p0, p1, Now.ps[j]);
		if (t1 < zero && t2 < zero){
			ret.ps[ret.n++] = Now.ps[i];
			ret.ps[ret.n++] = Now.ps[j];			
		}
		else if (t1 > zero && t2 > zero) continue;
		else {
			get_line(Now.ps[i], Now.ps[j], a2, b2, c2);
			tmp = get_point(a1, b1, c1, a2, b2, c2);
			if (t1 < zero){
				ret.ps[ret.n++] = Now.ps[i];
				ret.ps[ret.n++] = tmp;
			} else {
				ret.ps[ret.n++] = tmp;
				ret.ps[ret.n++] = Now.ps[j];
			}
		}
	}
	if (ret.n == 0) return ret;
	for (i = 1, j = 1; i < ret.n; i++)
		if (!same(ret.ps[i], ret.ps[i-1]))
			ret.ps[j++] = ret.ps[i];
	ret.n = j;
	if (j > 1 && same(ret.ps[0], ret.ps[j-1])) ret.n--;
	ret.ps[ret.n] = ret.ps[0];
	return ret;
}

void work()
{
	Ret = Pts;
	for (int i = 0; i < Pts.n; i++)
		Ret = calc(Pts.ps[i], Pts.ps[i+1], Ret);
	ans = 0;
	Tpoint p0; p0.x = 0; p0.y = 0;
	for (int i = 0; i < Ret.n; i++)
		ans += cross(p0, Ret.ps[i], Ret.ps[i+1]);
	ans /= 2; ans = Fabs(ans);
}

void print()
{
	printf("%.2f\n", ans);
}

int main()
{
	scanf("%d", &T);
	while (T){
		T--;
		init();
		work();
		print();
	}
	return 0;
}

• 好像还有问题哦…… (83) aoxboxcox 2011-04-25 16:05:54