2043.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"fstream.h"
#include"stdio.h"
#include"math.h"
//#include"time.h"
#include"algorithm"
//ifstream in("area.txt");
using namespace std;
//#define cin in
//////////////////////////////
#define Type double /*坐标类型*/
//////////////////////////////
struct point
{Type x,y;
point(){x=y=0;}
point(Type &x,Type &y):x(x),y(y){;}
bool operator==(point &a){return x==a.x&&y==a.y;}
};

struct line
{point a,b;
line(){;}
line(point &x,point &y):a(x),b(y)
{;}
};
////////////////////////////////////////////////////////////////
line l[110];
long xmin,ymin,xmax,ymax;
double ly[110];
int n,m;
struct piece
{
	float yl,yr;
}pc[110];
int cmp(piece a,piece b)
{
	return a.yl<b.yl||(a.yl==b.yl&&a.yr<b.yr);
}
void fillpiece(long x)
{
	line l1,l2;int i;		
	m=0;
	for(i=0;i<n;i++)
		if(l[i].a.x<=x&&x+1<=l[i].b.x)
		{
			pc[m].yl=l[i].a.y+ly[i]*(x-l[i].a.x);
			pc[m].yr=l[i].a.y+ly[i]*(x+1-l[i].a.x);
			m++;
		}
		pc[m].yl=ymin;
		pc[m].yr=ymin;
		m++;
		pc[m].yl=ymax;
		pc[m].yr=ymax;
		m++;

	sort(&pc[0],&pc[m],cmp);
}
void doit()
{
	long x,i,s,t;bool inside=0;double t1,t2;
	s=0;
	for(x=xmin;x<xmax;x++)
	{
		fillpiece(x);
		for(i=0;i<m;i+=2)
		{
			t1=pc[i+1].yl<pc[i+1].yr?pc[i+1].yl:pc[i+1].yr;
			t2=pc[i].yl>pc[i].yr?pc[i].yl:pc[i].yr;
			
			t1=floor(t1);
			if(t2-floor(t2)>0.0000001)t2=floor(t2)+1;
			
			t=(long)(t1-t2);
			if(t>0)s+=t;
		}
	}
	cout<<(ymax-ymin)*(xmax-xmin)-s<<endl;
	return ;
}
int cmp1(line l1,line l2)
{
	return l1.a.y<l2.a.y||(l1.a.y==l2.a.y&&l1.b.y<l2.b.y);
}
void init()
{
	xmin=20000;ymin=20000;ymax=-20000;xmax=-20000;
	int i;point a,b;
	for(i=0;i<n;i++)
	{
		cin>>a.x>>a.y;
		//scanf("%lf%lf",&a.x,&a.y);
		xmax=xmax>a.x?xmax:a.x;
		xmin=xmin<a.x?xmin:a.x;
		ymax=ymax>a.y?ymax:a.y;
		ymin=ymin<a.y?ymin:a.y;
		if(i)
		{
			l[i].a=a;l[i].b=b;
		}
		b=a;
	}
	l[0].a=l[1].b;l[0].b=b;
	for(i=0;i<n;i++)
	{
		if(l[i].a.x>l[i].b.x)
			swap(l[i].a,l[i].b);
	}
	sort(&l[0],&l[n],cmp1);
	for(i=0;i<n;i++)
	{
		ly[i]=(double)(l[i].b.y-l[i].a.y)/(l[i].b.x-l[i].a.x);
	}
	ymin--;
	ymax++;
}
int main()
{
//	long t=clock();
	while(1)
	{
		//scanf("%d",&n);
		cin>>n;
		if(n==0)break;
		init();
		doit();
	}
//	cout<<"   "<<clock()-t<<endl;
//	scanf("%ld",&t);
	return 0;
}