Problem: Example

Input

4 4
0 0
6 0
6 6
0 6


Output

35.759506

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;




struct Point{
	Point(double arg_x,double arg_y){
		x = arg_x;
		y = arg_y;
	}

	Point(){
		x = y = 0.0;
	}

	Point operator + (Point p){ return Point(x+p.x,y+p.y); }
	Point operator - (Point p){ return Point(x-p.x,y-p.y);}
	Point operator * (double a){ return Point(a*x,a*y); }
	Point operator / (double a){ return Point(x/a,y/a); }

	double abs(){ return sqrt(norm()); }
	double norm(){ return x*x + y*y; }

	bool operator<(const Point &p) const{
		return x != p.x? x < p.x: y < p.y;
	}

	bool operator == (const Point &p) const{
		return fabs(x-p.x) < EPS && fabs(y-p.y) < EPS;
	}

	double x,y;
};

typedef Point Vector;
typedef vector<Point> Polygon;

struct Circle{
	Point center;
	double r;
};

struct Line{
	Point p[2];
	Line(Point p1,Point p2){
		p[0] = p1;
		p[1] = p2;
	}
	Line(){

	}
};

int N;
double r;
double min_x,max_x,min_y,max_y;
bool is_out[15];
Polygon POLYGON;


double norm(Vector a){
	return a.x*a.x+a.y*a.y;
}

double abs(Vector a){
	return sqrt(norm(a));
}

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

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

Point project(Line l,Point p){

	Vector base = l.p[1]-l.p[0];
	double r = dot(p-l.p[0],base)/norm(base);
	return l.p[0]+base*r;
}

//円と直線の交点を求める関数
vector<Point> getCrossPoints(Circle c,Line l){

	vector<Point> ret;

	Vector pr = project(l,c.center);
	Vector e = (l.p[1]-l.p[0])/abs(l.p[1]-l.p[0]);

	double base;

	if(fabs(c.r*c.r-norm(pr-c.center)) < EPS){

		base = 0;
	}else{
		base = sqrt(c.r*c.r-norm(pr-c.center));
	}

	ret.push_back(Point(pr+e*base));
	ret.push_back(Point(pr-e*base));

	return ret;
}

Point calc_minus(Point a,Point b){
    Point ret;

    ret.x = a.x-b.x;
    ret.y = a.y-b.y;

    return ret;
}

double calc_len(Vector a){
    return sqrt(a.x*a.x+a.y*a.y);
}

double calc_slope(Line A){

	if(fabs(A.p[0].x-A.p[1].x) < EPS){

		return DBL_MAX;

	}else if(fabs(A.p[0].y-A.p[1].y) < EPS){

		return 0;

	}else{

		return (A.p[0].y-A.p[1].y)/(A.p[0].x-A.p[1].x);
	}
}

//★★線分ではなく直線と点の距離★★
double getDistanceLP(Line l,Point p){
    return fabs(cross(calc_minus(l.p[1],l.p[0]),calc_minus(p,l.p[0]))/calc_len(calc_minus(l.p[1],l.p[0])));
}

//★★点と線分の距離★★
double getDistanceSP(Line l,Point p){
	if(dot(calc_minus(l.p[1],l.p[0]),calc_minus(p,l.p[0])) < 0.0)return calc_len(calc_minus(p,l.p[0]));
	if(dot(calc_minus(l.p[0],l.p[1]),calc_minus(p,l.p[1])) < 0.0)return calc_len(calc_minus(p,l.p[1]));
	return getDistanceLP(l,p);
}

double calc_S(Polygon g){

	int N = g.size();
	double ret = 0;

	for(int i = 0; i < g.size(); i++){
		ret += cross(g[i],g[(i+1)%N]);
	}
	return ret/2.0;
}

double calc_dist(Point A,Point B){

	return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}

//交点を求める関数
Point calc_Cross_Point(double x1,double x2,double x3,double x4,double y1,double y2,double y3,double y4){
	Point ret;
	ret.x = ((x2-x1)*(y3*(x4-x3)+x3*(y3-y4))-(x4-x3)*(y1*(x2-x1)+x1*(y1-y2)))/((y2-y1)*(x4-x3)-(y4-y3)*(x2-x1));
	if(x1 != x2){
		ret.y = ((y2-y1)*ret.x+y1*(x2-x1)+x1*(y1-y2))/(x2-x1);
	}else{
		ret.y = ((y4-y3)*ret.x+y3*(x4-x3)+x3*(y3-y4))/(x4-x3);
	}
	return ret;
}

//インタフェース関数
Point calc_Cross_Point(Point a,Point b,Point c,Point d){
	return calc_Cross_Point(a.x,b.x,c.x,d.x,a.y,b.y,c.y,d.y);
}

Point calc_Cross_Point(Line A,Line B){

	if(getDistanceSP(B,A.p[0]) < EPS){

		return A.p[0];

	}else if(getDistanceSP(B,A.p[1]) < EPS){

		return A.p[1];

	}else if(getDistanceSP(A,B.p[0]) < EPS){

		return B.p[0];

	}else if(getDistanceSP(A,B.p[1]) < EPS){

		return B.p[1];
	}

	return calc_Cross_Point(A.p[0],A.p[1],B.p[0],B.p[1]);
}


//円とポリゴンの共通面積を求める
double calc_common_S(Circle circle,Polygon polygon){

	//それぞれの頂点が、円の内部にあるか否かを調べる
	for(int i = 0; i < N; i++){

		double tmp_dist = calc_dist(polygon[i],circle.center);

		if(tmp_dist <= circle.r){

			is_out[i] = false; //中

		}else{

			is_out[i] = true; //外
		}
	}

	double ret = 0;

	for(int i = 0; i < N; i++){

		Point left = polygon[i];
		Point right = polygon[(i+1)%N];

		Line tmp_line = Line(left,right);
		double tmp_dist = getDistanceSP(tmp_line,circle.center);

		if(is_out[i] == false && is_out[(i+1)%N] == false){ //両方中

			Polygon tmp;
			tmp.push_back(circle.center);
			tmp.push_back(right);
			tmp.push_back(left);


			ret += calc_S(tmp);

		}else if(is_out[i] == true && is_out[(i+1)%N] == true){ //両方外

			//printf("点%dと点%dは両方外\n",i,(i+1)%N);

			if(tmp_dist > circle.r){ //両方外かつ交点なし:扇形

				Vector vec1 = left-circle.center;
				Vector vec2 = right-circle.center;

				double theta = acos(dot(vec1,vec2)/(abs(vec1)*abs(vec2)));

				ret += (r*r*theta)/2;

			}else{ //交点あり

				vector<Point> cross_points = getCrossPoints(circle,Line(left,right));
				if(calc_dist(left,cross_points[1]) < calc_dist(left,cross_points[0])){

					swap(cross_points[0],cross_points[1]);
				}

				//左側扇形
				Vector vec1 = left-circle.center;
				Vector vec2 = cross_points[0]-circle.center;

				double theta = acos(dot(vec1,vec2)/(abs(vec1)*abs(vec2)));

				ret += (r*r*theta)/2;

				//三角形
				Polygon tmp;
				tmp.push_back(circle.center);
				tmp.push_back(cross_points[1]);
				tmp.push_back(cross_points[0]);

				ret += calc_S(tmp);

				//右側扇形
				Vector vec3 = cross_points[1]-circle.center;
				Vector vec4 = right-circle.center;

				double theta2 = acos(dot(vec3,vec4)/(abs(vec3)*abs(vec4)));

				ret += (r*r*theta2)/2;
			}

		}else{

			if(is_out[i] == true){ //leftが外

				vector<Point> cross_points = getCrossPoints(circle,Line(left,right));

				//leftに近い方が交点
				Point cross_point;
				if(calc_dist(left,cross_points[0]) < calc_dist(left,cross_points[1])){

					cross_point = cross_points[0];

				}else{

					cross_point = cross_points[1];
				}

				//左扇
				Vector vec1 = left-circle.center;
				Vector vec2 = cross_point-circle.center;

				double theta = acos(dot(vec1,vec2)/(abs(vec1)*abs(vec2)));

				ret += (r*r*theta)/2;

				//三角形
				Polygon tmp;
				tmp.push_back(circle.center);
				tmp.push_back(right);
				tmp.push_back(cross_point);

				ret += calc_S(tmp);

			}else{ //rightが外

				vector<Point> cross_points = getCrossPoints(circle,Line(left,right));

				//rightに近い方が交点
				Point cross_point;
				if(calc_dist(right,cross_points[0]) < calc_dist(right,cross_points[1])){

					cross_point = cross_points[0];

				}else{

					cross_point = cross_points[1];
				}

				//三角形
				Polygon tmp;
				tmp.push_back(circle.center);
				tmp.push_back(cross_point);
				tmp.push_back(left);

				ret += calc_S(tmp);

				//右扇
				Vector vec1 = cross_point-circle.center;
				Vector vec2 = right-circle.center;

				double theta = acos(dot(vec1,vec2)/(abs(vec1)*abs(vec2)));

				ret += (r*r*theta)/2;
			}
		}
	}

	return ret;
}


int func(double x1,double y1,double x2, double y2, double xp, double yp){
	double naiseki,norm1,norm2,gaiseki;
	norm1 = sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
	norm2 = sqrt((xp-x1)*(xp-x1)+(yp-y1)*(yp-y1));
	naiseki = (xp-x1)*(x2-x1)+(yp-y1)*(y2-y1);
	gaiseki = (x2-x1)*(yp-y1)-(xp-x1)*(y2-y1);
	if(gaiseki > EPS){
		return 1;
	}else if(gaiseki < -EPS){
		return -1;
	}
	if(naiseki < -EPS){
		return 2;
	}

	if(norm1 < norm2){
		return -2;
	}
	return 0;
}


bool is_Cross(Line a,Line b){

	if(func(a.p[0].x,a.p[0].y,a.p[1].x,a.p[1].y,b.p[0].x,b.p[0].y)*
			func(a.p[0].x,a.p[0].y,a.p[1].x,a.p[1].y,b.p[1].x,b.p[1].y) <= 0 &&
			func(b.p[0].x,b.p[0].y,b.p[1].x,b.p[1].y,a.p[0].x,a.p[0].y)*
			func(b.p[0].x,b.p[0].y,b.p[1].x,b.p[1].y,a.p[1].x,a.p[1].y) <= 0){
		return true;
	}
	return false;
}

double thirds_searchY(double X){

	double L = max_y,R = min_y;

	//交点を持つy座標の範囲を求める
	Line line = Line(Point(X,-1000),Point(X,1000));

	bool FLG = false;

	for(int i = 0; i < N; i++){

		Line tmp = Line(POLYGON[i],POLYGON[(i+1)%N]);

		if(is_Cross(line,tmp)){

			Point p = calc_Cross_Point(tmp,line);
			L = min(L,p.y);
			R = max(R,p.y);

			FLG = true;
		}
	}

	if(!FLG)return 0;


	for(int loop = 0; loop < 100; loop++){

		double mid1 = (2.0*L+R)/3.0;
		double mid2 = (1.0*L+2.0*R)/3.0;

		Circle circle1,circle2;

		circle1.center.x = X;
		circle1.center.y = mid1;
		circle1.r = r;

		circle2.center.x = X;
		circle2.center.y = mid2;
		circle2.r = r;

		if(calc_common_S(circle1,POLYGON) > calc_common_S(circle2,POLYGON)){

			R = mid2;
		}else{

			L = mid1;
		}
	}

	Circle circle;
	circle.center.x = X;
	circle.center.y = (L+R)/2;
	circle.r = r;

	return calc_common_S(circle,POLYGON);
}

double thirds_searchX(){

	double L = min_x,R = max_x;

	for(int loop = 0; loop < 100; loop++){

		double mid1 = (2.0*L+R)/3.0;
		double mid2 = (1.0*L+2.0*R)/3.0;

		if(thirds_searchY(mid1) > thirds_searchY(mid2)){

			R = mid2;
		}else{

			L = mid1;
		}
	}

	return thirds_searchY((L+R)/2);
}


int main(){

	scanf("%d %lf",&N,&r);

	min_x = BIG_NUM;
	min_y = BIG_NUM;

	max_x = -BIG_NUM;
	max_y = -BIG_NUM;

	for(int i = 0; i < N; i++){

		double x,y;
		scanf("%lf %lf",&x,&y);

		min_x = min(min_x,x);
		min_y = min(min_y,y);

		max_x = max(max_x,x);
		max_y = max(max_y,y);

		POLYGON.push_back(Point(x,y));
	}

	reverse(POLYGON.begin(),POLYGON.end());

	printf("%.10lf\n",thirds_searchX());

	return 0;
}