2574.txt

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

Problem Id:2574  User Id:fzk 
Memory:40K  Time:1357MS
Language:C++  Result:Accepted

Source 

#include"iostream.h"
#include"stdio.h"
#include"math.h"

#include"algorithm"

using namespace std;

//////////////////////////////
#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;}
};

inline Type cheng(point a,point b,point c)
{return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.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
{
	double yl,yr;
}pc[110];

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++;
	}

}

void doit()
{
	long x,i,t;double t1,t2;
	__int64 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;
			
			t=(long)t1-(long)(t2+0.999999);
			if(t>0)s+=t;
		}
	}

	printf("%I64d\n",s);
	return ;
}

int cmp1(line l1,line l2)
{
	double min = l1.a.x > l2.a.x ? l1.a.x : l2.a.x ,
		   max = l1.b.x < l2.b.x ? l1.b.x : l2.b.x ,
		   c = ( min + max ) / 2 ;
		
	return max > min && l1.a.y+(l1.b.y-l1.a.y)/(l1.b.x-l1.a.x)*(c-l1.a.x) < 
						l2.a.y+(l2.b.y-l2.a.y)/(l2.b.x-l2.a.x)*(c-l2.a.x) ;
}

void init()
{
	xmin=2000000;ymin=2000000;ymax=-2000000;xmax=-2000000;

	int i,j;point a,b;

	for( n=0; scanf( "%lf %lf", &a.x, &a.y ) == 2 ; n++ )
	{
		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(n)
		{
			l[n].a=a;l[n].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);
	}

	for( i=0;i<n; )
	{
		bool key;
		for( i=0,key=true; i<n&&key; i++ )
		for( j=i+1; j<n; j++ )
			if( cmp1( l[j], l[i] ) )
			{
				swap( l[j], l[i] );
				key = false;
				break;
			}
	}

	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()
{
	init();
	doit();
	return 0;
}