3171575_re.cc

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <math.h>
#define MAX 311
#define eps 1e-6

struct point
{
	double x, y;
};

struct polygon
{
	int n;
	point pt[MAX];
};

struct line
{
	double a, b, c;
};

double cross(point a,point b,point c)
{
	return (a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x);
}

line getLine(point a,point b)
{
	line ret;

	ret.a = b.y-a.y;
	ret.b = a.x-b.x;
	ret.c = b.x*a.y-b.y*a.x;
	return ret;
}

point line_intersection(line l1,line l2)
{
	point ret;

	if(fabs(l1.b)<1e-10)
	{
		ret.x = -l1.c/l1.a;
		ret.y = (-l2.c-l2.a*ret.x)/l2.b;
	}
	else
	{
		ret.x = (l1.c*l2.b-l1.b*l2.c)/(l1.b*l2.a-l2.b*l1.a);
		ret.y = (-l1.c-l1.a*ret.x)/l1.b;
	}
	return ret;
}

int isequal(point a,point b)
{
	if(a.x!=b.x||a.y!=b.y)
		return 0;
	return 1;
}

polygon polygon_cross(point a,point b,polygon p)
{
	int i;
	polygon newp;
	double v1, v2;
	line l1, l2;

	newp.n = 0;
	for(i = 0; i < p.n; i++)
	{
		v1 = cross(b,p.pt[i],a);
		v2 = cross(b,p.pt[i+1],a);
		if(v1==0&&v2==0)
		{
			newp.pt[newp.n++] = p.pt[i];
			newp.pt[newp.n++] = p.pt[i+1];
		}
		else
		{
			if(v1<0&&v2<0)
			{
				newp.pt[newp.n++] = p.pt[i];
				newp.pt[newp.n++] = p.pt[i+1];
			}
			else
			{
				if(v1*v2<=0)
				{
					l1 = getLine(a,b);
					l2 = getLine(p.pt[i],p.pt[i+1]);
					point intersection;
					intersection = line_intersection(l1,l2);
					if(v1 <= 0)
					{
						newp.pt[newp.n++] = p.pt[i];
						newp.pt[newp.n++] = intersection;
					}
					else
					{
						newp.pt[newp.n++] = intersection;
						newp.pt[newp.n++] = p.pt[i+1];
					}
				}
			}
		}
	}
	p.n = 0;
	if(newp.n==0)
		return p;
	p.pt[p.n++] = newp.pt[0];
	for(i = 1;i < newp.n;i++)
	{
		if(!isequal(newp.pt[i],newp.pt[i - 1]))
		{
			p.pt[p.n++] = newp.pt[i];
		}     
	}
	if(p.n!=1&&isequal(p.pt[p.n-1],p.pt[0]))
		p.n--;
	p.pt[p.n] = p.pt[0];
	return p;
}

double area_of_polygon(polygon p)
{
	int i, n;
	double area;

    n = p.n;
	area = 0;
	for(i = 1;i <= n;i++)
	{
		area += (p.pt[i-1].x*p.pt[i%n].y-p.pt[i%n].x*p.pt[i-1].y);
	}
	if(area < 0)
		area = -area;
	return area/2.0;
}

int main()
{
	int i, cas;
	polygon p, newp;
	double area;

	scanf("%d",&cas);
	while(cas-- > 0)
	{
		scanf("%d",&p.n);
		for(i = 0; i < p.n; i++)
		{
			scanf("%lf%lf",&p.pt[i].x,&p.pt[i].y);
		}
		p.pt[p.n] = p.pt[0];
		newp = p;
		for(i = 0; i < p.n; i++)
		{
			newp = polygon_cross(p.pt[i],p.pt[i+1],newp);
		}
		area = area_of_polygon(newp);
		printf("%.2lf\n",area);
	}
	return 0;
}