Problem: Magic Circle

Problem Statement

~ How to draw a magic circle ~

1. Prepare a sufficiently large and white floor.
2. Draw a circle with radii 1, 2, ..., R centered on the point at the floor coordinates (0,0).
3. Paint blue between the circle with radius 1 and the circle with radius 2, between the circle with radius 3 and the circle with radius 4, ... Do not paint outside the circle with radius R.
4. Draw a polygon with N vertices on the floor.
5. Repaint the white area inside the polygon with blue and the blue area with white.



It is said that the power of the magic circle becomes stronger as the magic circle contains more blue.
Therefore, I would like you to find the area of ​​the blue area included in the magic circle.

The following figure is an example of a magic circle that can be drawn by this procedure.

<image>

Constraints

* 3 ≤ N ≤ 100
* 1 ≤ R ≤ 100
* Polygons are included inside or on the circumference of a circle with radius R.
* Polygons do not have self-intersections.
* The vertices of the polygon are given in a counterclockwise order.

Input

Input follows the following format. All given numbers are integers.


N R
x_1 y_1
...
x_N y_N

(x_i, y_i) is the i-th vertex of the polygon.

Output

Output the area of ​​the blue area on one line.
The output value must have an absolute or relative error of less than 10 ^ {-8} with the true value.

Examples

Input

3 1
0 0
1 0
0 1


Output

0.500000000


Input

3 2
0 0
2 0
0 2


Output

8.995574288


Input

3 2
1 -1
1 1
-2 0


Output

11.123246567


Input

4 3
1 1
-1 1
-1 -1
1 -1


Output

11.707963268

Solution (in CPP):

Solution:
#include<cmath>
#include<cstdio>
#include<vector>
#include<algorithm>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

const double EPS=1e-8;
const double PI=acos(-1);

struct point{
	double x,y;
	point():x(0),y(0){}
	point(double x,double y):x(x),y(y){}
	point &operator+=(const point &a){ x+=a.x; y+=a.y; return *this; }
	point &operator-=(const point &a){ x-=a.x; y-=a.y; return *this; }
	point &operator*=(double c){ x*=c; y*=c; return *this; }
	point &operator/=(double c){ x/=c; y/=c; return *this; }
	point operator+(const point &a)const{ return point(x+a.x,y+a.y); }
	point operator-(const point &a)const{ return point(x-a.x,y-a.y); }
	point operator/(double c)const{ return point(x/c,y/c); }
	point operator-()const{ return point(-x,-y); }
	bool operator< (const point &a)const{ return x+EPS<a.x || abs(x-a.x)<EPS && y+EPS<a.y; }
	bool operator==(const point &a)const{ return abs(x-a.x)<EPS && abs(y-a.y)<EPS; }
	bool operator!=(const point &a)const{ return abs(x-a.x)>EPS || abs(y-a.y)>EPS; }
};

point operator*(double c,const point &a){ return point(c*a.x,c*a.y); }

double dot(const point &a,const point &b){ return a.x*b.x+a.y*b.y; }

double cross(const point &a,const point &b){ return a.x*b.y-a.y*b.x; }

double abs(const point &a){ return sqrt(a.x*a.x+a.y*a.y); }

double abs2(const point &a){ return a.x*a.x+a.y*a.y; }

point rot(const point &a,double theta){ return point(a.x*cos(theta)-a.y*sin(theta),a.x*sin(theta)+a.y*cos(theta)); }

double arg(const point &a){ double t=atan2(a.y,a.x); return t<0?t+2*PI:t; }

struct line{
	point a,b;
	line(){}
	line(const point &a,const point &b):a(a),b(b){}
};

struct segment{
	point a,b;
	segment(){}
	segment(const point &a,const point &b):a(a),b(b){}
	operator line()const{ return line(a,b); }
};

typedef vector<point> polygon;

struct circle{
	point c;
	double r;
	circle():c(point(0,0)),r(0){}
	circle(const point &c,double r):c(c),r(r){}
};

point proj(const point &p,const line &L){ return L.a+dot(p-L.a,L.b-L.a)/abs2(L.b-L.a)*(L.b-L.a); }

enum{CCW=1,CW=-1,ON=0};
int ccw(const point &a,const point &b,const point &c){
	double rdir=cross(b-a,c-a);
	if(rdir> EPS) return CCW;
	if(rdir<-EPS) return CW;
	return ON;
}

double area(const point &a,const point &b,const point &c){
	return abs(cross(b-a,c-a))/2;
}

bool cover(const segment &S,const point &p){
	return abs(cross(S.a-p,S.b-p))<EPS && dot(S.a-p,S.b-p)<EPS;
}

bool cover(const polygon &F,const point &p){
	int n=F.size();
	bool res=false;
	rep(i,n){
		point v1=F[i]-p,v2=F[(i+1)%n]-p;
		if(v1.y>v2.y) swap(v1,v2);
		if(v1.y<EPS && EPS<v2.y && cross(v1,v2)>EPS) res=!res;
		if(abs(cross(v1,v2))<EPS && dot(v1,v2)<EPS) return true;
	}
	return res;
}

bool intersect(const segment &S1,const segment &S2){
	if(max(S1.a.x,S1.b.x)+EPS<min(S2.a.x,S2.b.x)
	|| max(S1.a.y,S1.b.y)+EPS<min(S2.a.y,S2.b.y)
	|| max(S2.a.x,S2.b.x)+EPS<min(S1.a.x,S1.b.x)
	|| max(S2.a.y,S2.b.y)+EPS<min(S1.a.y,S1.b.y)) return false;
	return ccw(S1.a,S1.b,S2.a)*ccw(S1.a,S1.b,S2.b)<=0
		&& ccw(S2.a,S2.b,S1.a)*ccw(S2.a,S2.b,S1.b)<=0;
}

point get_intersect(const segment &S1,const segment &S2){
	double a1=cross(S1.b-S1.a,S2.b-S2.a);
	double a2=cross(S1.b-S1.a,S1.b-S2.a);
	if(abs(a1)<EPS){
		if(cover(S1,S2.a)) return S2.a;
		if(cover(S1,S2.b)) return S2.b;
		if(cover(S2,S1.a)) return S1.a;
		return S1.b;
	}
	return S2.a+a2/a1*(S2.b-S2.a);
}

int get_intersect(const circle &C,const segment &S,vector<point> &res){
	point h=proj(C.c,S);
	double d=abs(C.c-h);
	if(d>C.r+EPS) return 0;
	if(d>C.r-EPS){
		int cnt=0;
		if(cover(S,h)) res.push_back(h), cnt++;
		return cnt;
	}
	else{
		point v=S.b-S.a;
		v*=sqrt(C.r*C.r-d*d)/abs(v);
		int cnt=0;
		if(cover(S,h+v)) res.push_back(h+v), cnt++;
		if(cover(S,h-v)) res.push_back(h-v), cnt++;
		return cnt;
	}
}

bool eq(const double &a,const double &b){ return abs(a-b)<EPS; }

int main(){
	const point o(0,0);

	point cen;
	do{
		cen=point(rand()%1000/1000.0,rand()%1000/1000.0);
	}while(abs(cen)<0.1 || 0.9<abs(cen));

	int n,R; scanf("%d%d",&n,&R);
	polygon F(n);
	rep(i,n) scanf("%lf%lf",&F[i].x,&F[i].y);

	vector<double> theta;
	rep(i,n){
		theta.push_back(arg(F[i]-cen));
		vector<point> Q;
		for(int r=1;r<=R;r++){
			get_intersect(circle(o,r),segment(F[i],F[(i+1)%n]),Q);
		}
		rep(j,Q.size()) theta.push_back(arg(Q[j]-cen));
	}
	theta.push_back(0);
	theta.push_back(PI/2);
	theta.push_back(PI);
	theta.push_back(3*PI/2);

	sort(theta.begin(),theta.end());
	theta.erase(unique(theta.begin(),theta.end(),eq),theta.end());

	double ans=0;
	rep(i,theta.size()){
		double t1=theta[i],t2=theta[(i+1)%theta.size()];
		if(t2<t1) t2+=2*PI;

		segment H1(cen,cen+rot(point(R+1,0),t1));
		segment H2(cen,cen+rot(point(R+1,0),t2));

		vector<double> A;
		for(int r=1;r<=R;r++){
			vector<point> tmp;
			get_intersect(circle(o,r),H1,tmp);
			get_intersect(circle(o,r),H2,tmp);
			double s1=arg(tmp[0]),s2=arg(tmp[1]);
			if(s2<s1) s2+=2*PI;
			A.push_back(r*r*(s2-s1)/2-area(o,tmp[0],tmp[1])+area(cen,tmp[0],tmp[1]));
		}
		rep(j,F.size()){
			segment S(F[j],F[(j+1)%n]);
			if(abs(cross(S.b-S.a,S.b-cen))>EPS && intersect(S,H1) && intersect(S,H2)){
				point a=get_intersect(S,H1);
				point b=get_intersect(S,H2);
				A.push_back(area(cen,a,b));
			}
		}
		sort(A.begin(),A.end());

		if(cover(F,cen)){
			A.insert(A.begin(),0);
		}
		for(int j=1;j<A.size();j+=2) ans+=A[j]-A[j-1];
	}

	printf("%.9f\n",ans);

	return 0;
}