Problem: Example

Input

4 6 5
-2 5
-2 -1
2 -1
2 5
-2 1
-2 0
0 0
0 -2
2 -2
2 1


Output

8

Solution (in CPP):

Solution:
#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
const double EPS=1e-10;
const double INF=1e+10;
const double PI=acos(-1);
int sig(double r){return (r<-EPS)?-1:(r>+EPS)?+1:0;}
double ABS(double a){return max(a,-a);}
struct Pt{
	double x,y;
	Pt(){}
	Pt(double x,double y):x(x),y(y){}
	Pt operator+(const Pt &a)const{return Pt(x+a.x,y+a.y);}
	Pt operator-(const Pt &a)const{return Pt(x-a.x,y-a.y);}
	Pt operator*(const Pt &a)const{return Pt(x*a.x-y*a.y,x*a.y+y*a.x);}
	Pt operator-()const{return Pt(-x,-y);}
	Pt operator*(const double &k)const{return Pt(x*k,y*k);}
	Pt operator/(const double &k)const{return Pt(x/k,y/k);}
	double ABS()const{return sqrt(x*x+y*y);}
	double abs2()const{return x*x+y*y;}
	double arg()const{return atan2(y,x);}
	double dot(const Pt &a)const{return x*a.x+y*a.y;}
	double det(const Pt &a)const{return x*a.y-y*a.x;}
};
double tri(const Pt &a,const Pt &b,const Pt &c){return (b-a).det(c-a);}
int iSP(Pt a,Pt b,Pt c){
	int s=sig((b-a).det(c-a));
	if(s)return s;
	if(sig((b-a).dot(c-a))<0)return -2;
	if(sig((a-b).dot(c-b))<0)return +2;
	return 0;
}

int iLL(Pt a,Pt b,Pt c,Pt d){
	if(sig((b-a).det(d-c)))return 1;
	if(sig((b-a).det(c-a)))return 0;
	return -1;
}
int iSS(Pt a,Pt b,Pt c,Pt d){
	return (iSP(a,b,c)*iSP(a,b,d)<=0&&iSP(c,d,a)*iSP(c,d,b)<=0);
}
double dLP(Pt a,Pt b,Pt c){
	return ABS(tri(a,b,c))/(b-a).ABS();
}
double dSP(Pt a,Pt b,Pt c){
	if(sig((b-a).dot(c-a))<=0)return (c-a).ABS();
	if(sig((a-b).dot(c-b))<=0)return (c-b).ABS();
	return ABS(tri(a,b,c))/(b-a).ABS();
}
bool iCS(Pt a,double r,Pt b,Pt c){
	return (sig(r-dSP(b,c,a))>=0&&sig(r-max((b-a).ABS(),(c-a).ABS()))<=0);
}
pair<Pt,Pt>pCL(Pt a,double r,Pt b,Pt c){
	Pt h=b+(c-b)*(c-b).dot(a-b)/(c-b).abs2();
	double d=(h-a).ABS();
	double y=sqrt(max(r*r-d*d,0.0));
	Pt e=(c-b)/(c-b).ABS();
	return make_pair(h-e*y,h+e*y);
}
pair<Pt,Pt>pCC(Pt a,double r,Pt b,double s){
	double d=(b-a).ABS();
	double x=(d*d+r*r-s*s)/(d*2);
	Pt e=(b-a)/d,w=e*Pt(0,1)*sqrt(max(r*r-x*x,0.0));
	return make_pair(a+e*x-w,a+e*x+w);
}
int sGP(int n,Pt p[],Pt a){
	int side=-1,i;
	p[n]=p[0];
	for(i=0;i<n;i++){
		Pt p0=p[i]-a,p1=p[i+1]-a;
		if(sig(p0.det(p1))==0&&sig(p0.dot(p1))<=0)return 0;
		if(p0.y>p1.y)swap(p0,p1);
		if(sig(p0.y)<=0&&0<sig(p1.y)&&sig(p0.det(p1))>0)side=-side;
	}
	return side;
}
int X1[30];
int Y1[30];
int X2[30];
int Y2[30];
Pt p1[30];
Pt p2[30];
Pt ce[30];
int ev[11000];
double dt[11000];
inline int rdown(double a){
	if(a>=0)return (int)a;
	double b=-a;
	return -((int)b+1);
}
int main(){
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	for(int i=0;i<a;i++){
		scanf("%d%d",X1+i,Y1+i);
		p1[i]=Pt((double)X1[i],(double)Y1[i]);
		X1[a]=X1[0];Y1[a]=Y1[0];
	}
	for(int i=0;i<b;i++){
		scanf("%d%d",X2+i,Y2+i);
		X2[i]+=c;
		p2[i]=Pt((double)X2[i],(double)Y2[i]);
		ce[i]=p2[i];
		ce[i].x-=(double)c;
		X2[b]=X2[0];Y2[b]=Y2[0];
	}
	ce[b]=ce[0];
	double r=(double)c;
	int ret=0;
	for(int i=-10000;i<=10000;i++){
		int sz=0;
		for(int j=0;j<a;j++){
			if(Y1[j]!=Y1[j+1]&&min(Y1[j],Y1[j+1])<=i&&i<=max(Y1[j],Y1[j+1])){
				ev[sz++]=X1[j];
			}
		}
		std::sort(ev,ev+sz);
	//	if(sz)printf("%d: \n",i);
		for(int j=0;j<sz-1;j++){
		//	printf("%d %d\n",ev[j],ev[j+1]);
		//	bool dame=false;
		//	for(int k=0;k<a;k++)if(i==Y1[k]&&i==Y1[k+1]&&min(X1[k],X1[k+1])==ev[j]&&ev[j+1]==max(X1[k],X1[k+1]))dame=true;
		//	if(dame)continue;
			if(sGP(a,p1,Pt((double)(ev[j]+ev[j+1])/2,(double)i))!=1)continue;
			double L=(double)ev[j]+0.2;
			double R=(double)ev[j+1]-0.2;
			double y=(double)i;
			int n=0;
			for(int k=0;k<b;k++){
				if(X2[k]==X2[k+1]){
					if(iSS(Pt(100000.0,y),Pt(-100000.0,y),Pt(ce[k].x-r,ce[k].y),Pt(ce[k].x-r,ce[k+1].y))){
						dt[n++]=ce[k].x-r;
						dt[n++]=ce[k].x+r;
					}
				}else{
					
				}
				if(iCS(ce[k],r,Pt(-100000,y),Pt(100000,y))){
					pair<Pt,Pt> u=pCL(ce[k],r,Pt(-100000,y),Pt(100000,y));
					dt[n++]=u.first.x;
					dt[n++]=u.second.x;
				}
			}
			dt[n++]=L;
			dt[n++]=R;
			std::sort(dt,dt+n);
			bool last=true;
			for(int k=0;k<n-1;k++){
				if(dt[k+1]-dt[k]<EPS/2)continue;
				if(dt[k]<L||dt[k+1]>R)continue;
				double M=(dt[k]+dt[k+1])/2;
				Pt mid=Pt(M,y);
				bool ok=false;
				for(int l=0;l<b;l++){
					bool c1=false;
					bool c2=false;
					bool c3=false;
					bool c4=false;
					bool rec=false;
					if((mid-ce[l]).ABS()<r-EPS){
						c1=true;
					}
					if((mid-ce[l]).ABS()<r+EPS){
						c3=true;
					}
					if((mid-ce[l+1]).ABS()<r-EPS){
						c2=true;
					}
					if((mid-ce[l+1]).ABS()<r+EPS){
						c4=true;
					}
					if(X2[l]==X2[l+1]){
						if(ce[l].x-r-EPS<M&&M<ce[l].x+r+EPS&&min(ce[l].y,ce[l+1].y)-EPS<y&&y<max(ce[l].y,ce[l+1].y)+EPS)rec=true;
					}else{
						if(min(ce[l].x,ce[l+1].x)-EPS<M&&M<max(ce[l].x,ce[l+1].x)+EPS&&ce[l].y-r-EPS<y&&y<ce[l].y+r+EPS)rec=true;
					}
					if((rec||c3||c4)&&!(c1&&c2)){
						ok=true;break;
					}
				}
				if(!ok){
				
					int rm=rdown(dt[k+1]-EPS);
					int lm=rdown(dt[k]+EPS);
					ret+=rm-lm;
					if(!last){
						int rd=rdown(dt[k]+0.5);
						if(ABS(dt[k]-rd)<EPS)ret++;
					}
					last=false;
				}else last=true;
			}
			
		}
		//if(-3<i&&i<10)printf("%d: %d\n",i,ret);
	}
	printf("%d\n",ret);
}