code:
#include <queue>
#include <vector>
#include <fstream>
#include <iostream>
#include <algorithm>
using namespace std;
#include <ctime>
struct point {
int x,y;
point (int x1,int y1) : x(x1) , y(y1) {}
};
struct dpoint {
double x,y;
dpoint (double x1,double y1) : x(x1) , y(y1) {}
};
struct region{
int x1,y1,x2,y2; // up_left & down_right of each region
int area;
int banner ; // 0 means free,1 means availble,2 means obstacle
};
struct line {
int x1,y1,x2,y2; // x2>x1 & y2>y1
line (int x3,int y3,int x4,int y4) : x1(x3) , x2(x4) , y1(y3) , y2(y4) {}
};
double whichside (point a,point b,dpoint c){
return ( ( a.x * b.y ) - ( b.x * a.y ) + ( b.x * c.y ) - ( c.x * b.y ) + ( c.x * a.y ) - ( a.x * c.y ) );
}
bool isfree (const region &r ,const vector <line> &v ,const vector <line> &h ){
int up=0,right=0;
double x=double (r.x1+r.x2)/2 , y = double (r.y1+r.y2) /2 ;
for (int i=0;i<h.size();++i)
if ( whichside ( point (h[i].x1,h[i].y1) , point (h[i].x2,h[i].y1) , dpoint ((double)x,(double)y) ) < 0 && x>h[i].x1 && x<h[i].x2)
++up ;
for (int i=0;i<v.size();++i)
if ( whichside ( point (v[i].x1,v[i].y1) , point (v[i].x1,v[i].y2) , dpoint ((double)x,(double)y) ) < 0 && y>v[i].y1 && y<v[i].y2)
++right;
if ( right%2==0 && up%2==0 )
return true;
return false;
}
int main(){
clock_t cl=clock();
ifstream in ("sharif_00_i.in");
int T; in >>T;
while (T--){
int length,width; in >> length >> width;
vector <line> vertical , horizontal;
vector <int> xs,ys; // we need this cordinates to create region matrix
vector <int> ::iterator x_end,y_end;
xs.push_back(0);xs.push_back(length);
ys.push_back(0);ys.push_back(width);
int n,m; in >> n;
for (int b=0;b<n;++b){
in >> m;
point t(0,0), t2(0,0);
in >> t.x >> t.y; /*t.x-- , t.y-- ;*/
xs.push_back(t.x) ; ys.push_back(t.y);
int X,Y ; // for lines that not given
X=t2.x=t.x ; Y=t2.y=t.y;
for (int i=1;i<m;++i){
in >> t.x >> t.y; /*t.x-- , t.y-- ;*/
xs.push_back(t.x) ; ys.push_back(t.y);
if ( t.x != t2.x )
horizontal.push_back ( line (min(t.x,t2.x),min(t.y,t2.y),max(t.x,t2.x),max(t.y,t2.y)));
else
vertical.push_back ( line (min(t.x,t2.x),min(t.y,t2.y),max(t.x,t2.x),max(t.y,t2.y)));
t2.x=t.x , t2.y=t.y;
}
if ( X != t2.x )
horizontal.push_back ( line (min(X,t2.x),min(Y,t2.y),max(X,t2.x),max(Y,t2.y)));
else
vertical.push_back ( line (min(X,t2.x),min(Y,t2.y),max(X,t2.x),max(Y,t2.y)));
}
// stupidly sort :
sort (xs.begin(),xs.end());
sort ( ys.begin(),ys.end());
x_end = unique (xs.begin(),xs.end());
y_end = unique(ys.begin(),ys.end());
xs.erase( x_end , xs.end() );
ys.erase(y_end , ys.end() );
//create matrix :
vector <vector < region > > r (xs.size()-1 , vector <region> (ys.size()-1) );
for (int i=0;i<xs.size()-1;++i){
for (int j=0;j<ys.size()-1;++j){
r[i][j].x1=xs[i]; r[i][j].x2=xs[i+1];
r[i][j].y1=ys[j]; r[i][j].y2=ys[j+1];
r[i][j].area = ( (xs[i+1]-xs[i])*(ys[j+1]-ys[j]) );
}
}
for (int i=0;i<r.size();++i)
for (int j=0;j<r[i].size();++j)
if (! isfree( r[i][j], vertical , horizontal ) )
r[i][j].banner=2 ; // obstacle
queue <point> q;
q.push(point(r.size()-1,0));
while (!q.empty() ){
point p=q.front() ; q.pop();
if (r[p.x][p.y].banner==2)
continue;
r[p.x][p.y].banner=1; //available
if ( p.x > 0 && r[p.x-1][p.y].banner==0 )
q.push(point(p.x-1,p.y));
if ( p.y < r[p.x].size()-1 && r[p.x][p.y+1].banner==0 )
q.push(point(p.x,p.y+1));
}
int ans=0;
for (int i=0;i<r.size();++i)
for (int j=0;j<r[i].size();++j)
if (r[i][j].banner==0)
ans+=r[i][j].area;
cout << ans << endl;
}
cout << "Time: " << (clock() - cl ) * 0.001 << endl;
return 0;
}
// mohammad reza :D
