1689.txt

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

#include"iostream.h"
#include"vector"
#include"algorithm"
#define max(x,y) (((x)>(y))?(x):(y))
#define min(x,y) (((x)<(y))?(x):(y))

using namespace std;

struct point
{long x,y;};

struct type_dbx
{int n;
point d[50];	
};

type_dbx dbx[50];

vector <long> x,y;
long mx,my;
int n;

char sign[50*50*2];


inline long cheng(point a,point b,point c)
{return (a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x);}


int in(point p[50],int n,point judge)
{int c,k,j;point up,low,temp;
 c=0;
   j=0;
   while(p[j].y==judge.y)j++;
   for(;j<n;j=k)
  {k=j+1;
	while(p[k%n].y==judge.y&&p[k%n].x>judge.x)k++;
	up=p[j];
	low=p[k%n];

	if(up.y<low.y){temp=up;up=low;low=temp;}

	if(up.y<judge.y||low.y>judge.y)continue;

	if(cheng(low,up,judge)<=0&&k==j+1)continue;
	c++;
	}
   return c%2;
}
	

int com(long a,long b)
{return a>b;}

int main()
{int t,m,i,j,k,h,l;long s,xz[50*50+4],yz[50*50+4];
	point p;
	cin>>t;	
	while(t--)
	{cin>>mx>>my>>n;
	mx*=2;my*=2;
	m=2;
	xz[0]=0;yz[0]=0;
	xz[1]=mx;yz[1]=my;
	
	for(i=0;i<n;i++)
	{cin>>dbx[i].n;
	
	for(j=0;j<dbx[i].n;j++)
		{cin>>dbx[i].d[j].x>>dbx[i].d[j].y;
		dbx[i].d[j].y=my/2-dbx[i].d[j].y;
		dbx[i].d[j].x*=2;
		dbx[i].d[j].y*=2;                        
	      	xz[m]=dbx[i].d[j].x;yz[m]=dbx[i].d[j].y;m++;
		}
	}
	x.resize(m);
	y.resize(m);
	for(i=0;i<m;i++){x[i]=xz[i];y[i]=yz[i];}	
	sort(x.begin(),x.end(),com);
	sort(y.begin(),y.end(),com);	
	for(i=0;i<m+2;i++)sign[i]=0;	
	sign[1]=1;	
	s=0;
	for(i=0;i<m-1;i++)
	{
	for(j=1;j<=m-1;j++)	
	{h=i;k=j-1;
	for(l=0;l<n;l++)
	   {p.x=x[k]-1;
	    p.y=y[h]-1;
	   if(in(dbx[l].d,dbx[l].n,p))break;
	    }
	if(l<n){sign[j]=0;continue;}
					
	if(sign[j]||sign[j-1])sign[j]=1;
			
	else {sign[j]=0;s+=(x[k]-x[k+1])*(y[h]-y[h+1]);}
//		cout<<x[k]<<' '<<x[k+1]<<' '<<y[h]<<' '<<y[h+1]<<endl;}
	
	}
	}
		cout<<s/4<<endl;
	}
return 0;
}