# 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.