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 <iostream>
#include <complex>
#include <vector>
#include <algorithm>
#include <utility>
#include <cmath>
using namespace std;
const double EPS = 1e-8;
const double INF = 1e12;
#define EQ(n,m) (abs((n)-(m)) < EPS)
#define X real()
#define Y imag()

typedef complex<double> P;
typedef vector<P> VP;

double dot(P a, P b){
    return (conj(a)*b).X;
}
double cross(P a, P b){
    return (conj(a)*b).Y;
}
int in_poly(const P &p, const VP &poly){
    int n = poly.size();
    int ret = -1;
    for(int i=0; i<n; i++){
        P a = poly[i]-p;
        P b = poly[(i+1)%n]-p;
        if(a.Y > b.Y) swap(a,b);
        if(abs(cross(a,b))<EPS && dot(a,b)<EPS) return 0;
        if(a.Y<=0 && b.Y>0 && cross(a,b)<0) ret = -ret;
    }
    return ret;
}

int solve(const VP &plane, const VP &cutter, double L){
    int m = plane.size();
    int n = cutter.size();
    
    //すべての格子線(タテ)について
    long long int ret = 0;
    for(int x=-10000; x<=10000; x++){
        vector<pair<double, double> > removed;
        
        //planeの外部
        vector<double> cp_y; //cross point y
        for(int i=0; i<m; i++){
            P curr = plane[i];
            P next = plane[(i+1)%m];
            if(EQ(curr.X, next.X)) continue;
            if(curr.X > next.X) swap(curr, next); //nextが右
            if(curr.X -EPS < x && x < next.X +EPS){
                cp_y.push_back(curr.Y);
            }
        }
        
        if(cp_y.empty()) continue;
        cp_y.push_back(-INF);
        cp_y.push_back(INF);
        sort(cp_y.begin(), cp_y.end());
        for(int i=0; i<(int)cp_y.size()-1; i++){
            if(in_poly(P(x, (cp_y[i] +cp_y[i+1])/2), plane) <= 0){
                removed.push_back(make_pair(cp_y[i], cp_y[i+1]));
            }
        }
        
        //辺でカットされる部分
        for(int i=0; i<n; i++){
            P curr = cutter[i];
            P next = cutter[(i+1)%n];
            if(EQ(curr.X, next.X)){ //縦に並ぶ
                if(curr.Y > next.Y) swap(curr, next); //nextが上
                if(x < curr.X -L -EPS || next.X +L +EPS < x) continue;
                double d = sqrt(L*L -(x-curr.X)*(x-curr.X));
                if(curr.Y +d > next.Y -d){
                    removed.push_back(make_pair(curr.Y -d, next.Y -d));
                    removed.push_back(make_pair(curr.Y +d, next.Y +d));
                }else{
                    removed.push_back(make_pair(curr.Y -d, next.Y +d));
                }
            }else{ //横に並ぶ
                if(curr.X > next.X) swap(curr, next); //nextが右
                if(x < curr.X -L -EPS || next.X +L +EPS < x) continue;
                double midx = (curr.X + next.X)/2;
                double nx = (x > midx)? 2*midx -x : x;
                double cd = sqrt(L*L -(nx -curr.X)*(nx -curr.X));
                double up = (nx < curr.X)? curr.Y +cd : curr.Y +L;
                double down = (nx < curr.X)? curr.Y -cd : curr.Y -L;
                if(nx < next.X -L){
                	removed.push_back(make_pair(down, up));
                }else{
                	double nd = sqrt(L*L -(nx -next.X)*(nx -next.X));
                	removed.push_back(make_pair(down, curr.Y -nd));
                    removed.push_back(make_pair(curr.Y +nd, up));
                }
            }
        }
        
        //残った格子点を加える
        sort(removed.begin(), removed.end());
        double last = -INF;
        for(int i=0; i<(int)removed.size()-1; i++){
            last = max(last, removed[i].second);
            if(last +EPS > removed[i+1].first) continue;
            double upper = floor(removed[i+1].first -EPS);
            double lower = ceil(last +EPS);
            ret += (int)(upper -lower +1 +0.5);
        }
    }
    return ret;
}

int main(){
    //input
    int m,n,L;
    cin >> m >> n >> L;
    
    VP plane(m), cutter(n);
    double x,y;
    for(int i=0; i<m; i++){
        cin >> x >> y;
        plane[i] = P(x, y);
    }
    for(int i=0; i<n; i++){
        cin >> x >> y;
        cutter[i] = P(x, y);
    }
    
    cout << solve(plane, cutter, L) << endl;
    return 0;
}