Poj Solution 1689

http://poj.org/problem?id=1689

#include<iostream>
#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;
}


											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *