Problem: Example

Input

4 4
0 0
6 0
6 6
0 6


Output

35.759506

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const double EPS = 1e-8;
const double PI = acos(-1.0);
struct point
{
	double x,y;
	point() {}
	point(double a,double b) : x(a),y(b) {}
	friend point operator + (const point &a,const point &b)
	{
		return point(a.x+b.x,a.y+b.y);
	}
	friend point operator - (const point &a,const point &b)
	{
		return point(a.x-b.x,a.y-b.y);
	}
	friend point operator * (const point &a,const double &b)
	{
		return point(a.x*b,a.y*b);
	}
	friend point operator * (const double &a,const point &b)
	{
		return point(a*b.x,a*b.y);
	}
	friend point operator / (const point &a,const double &b)
	{
		return point(a.x/b,a.y/b);
	}
};
point res[15],temp[15];
double r;
int n;
int dcmp(double k)
{
	return k < -EPS ? -1 : k > EPS ? 1 : 0;
}
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 &o)
{
	return sqrt(dot(o,o));
}
point crosspt(const point &a,const point &b,const point &p,const point &q)
{
	double a1 = cross(b - a,p - a);
	double a2 = cross(b - a,q - a);
	return (p*a2 - q*a1)/(a2 - a1);
}
double mysqrt(double n)
{
	return sqrt(max(0.0,n));
}
double sector_area(const point &a,const point &b)
{
	double theta = atan2(a.y,a.x) - atan2(b.y,b.x);
	while(theta <= 0) theta += 2*PI;
	while(theta > 2*PI) theta -= 2*PI;
	theta = min(theta,2*PI - theta);
	return r * r * theta / 2;
}
void circle_cross_line(point a,point b,point o,double r,point ret[],int &num)
{
	double x0 = o.x,y0 = o.y;
	double x1 = a.x,y1 = a.y;
	double x2 = b.x,y2 = b.y;
	double dx = x2 -x1,dy = y2 - y1;
	double A = dx*dx + dy*dy;
	double B = 2*dx*(x1 - x0) + 2*dy*(y1 - y0);
	double C = (x1 -x0)*(x1 - x0) + (y1 - y0)*(y1 - y0) - r*r;
	double delta = B*B - 4*A*C;
	num = 0;
	if(dcmp(delta) >= 0)
	{
		double t1 = (-B - mysqrt(delta))/(2*A);
		double t2 = (-B + mysqrt(delta))/(2*A);
		if(dcmp(t1-1) <= 0 && dcmp(t1) >= 0)
		{
			ret[num++] = point(x1 + t1*dx,y1 + t1*dy);
		}
		if(dcmp(t2-1) <= 0 && dcmp(t2) >= 0)
		{
			ret[num++] = point(x1 + t2*dx,y1 + t2*dy);
		}
	}
}
double cacl(const point &a,const point &b)
{
	point p[2];
	int num = 0;
	int ina = dcmp(abs(a) - r) < 0;
	int inb = dcmp(abs(b) - r) < 0;
	if(ina)
	{
		if(inb) return fabs(cross(a,b))/2.0;
		else 
		{
			circle_cross_line(a,b,point(0,0),r,p,num);
			return sector_area(b,p[0]) + fabs(cross(a,p[0]))/2.0;
		}
	}
	else 
	{
		if(inb)
		{
			circle_cross_line(a,b,point(0,0),r,p,num);
			return sector_area(p[0],a) + fabs(cross(p[0],b)) / 2.0;
		}
		else 
		{
			circle_cross_line(a,b,point(0,0),r,p,num);
			if(num == 2)
			{
				return sector_area(a,p[0]) + sector_area(p[1],b) + fabs(cross(p[0],p[1])) / 2.0;
			}
			else return sector_area(a,b);
		}
	}	
}
double area()
{
	double ret = 0;
	for(int i = 0;i < n;i++)
	{
		int sgn = dcmp(cross(res[i],res[i+1]));
		if(sgn != 0) ret += sgn*cacl(res[i],res[i+1]);
	}
	return ret;
}

double pol_area()
{
	double tarea = 0;
	for (int i = 1; i < n; i++)
		tarea += fabs(cross(temp[i] - temp[0], temp[i + 1] - temp[0]));
	return tarea / 2;
}

point MassCenter()
{
	point ans = point(0,0);
	double tarea = pol_area();
	if (dcmp(tarea) == 0) return ans;
	for (int i = 0; i < n; i++) ans = ans + (temp[i] + temp[i + 1]) * cross(temp[i], temp[i + 1]);
	return ans / tarea / 6;
}

double get_ymin(double x)
{
	double y = 500;
	for (int i = 0; i < n; i++)
	{
		if (dcmp((temp[i].x - x) * (temp[i + 1].x - x)) <= 0)
		{
			if (dcmp(temp[i].x - temp[i + 1].x) == 0) {
				y = min(y, min(temp[i].y, temp[i + 1].y));
			} else {
				double rat = (x - temp[i].x) / (temp[i + 1].x - temp[i].x);
				y = min(y, rat * (temp[i + 1].y - temp[i].y) + temp[i].y);
			}
		}
	}
	return y;
}

double get_ymax(double x)
{
	double y = -100;
	for (int i = 0; i < n; i++)
	{
		if (dcmp((temp[i].x - x) * (temp[i + 1].x - x)) <= 0)
		{
			if (dcmp(temp[i].x - temp[i + 1].x) == 0) {
				y = max(y, max(temp[i].y, temp[i + 1].y));
			} else {
				double rat = (x - temp[i].x) / (temp[i + 1].x - temp[i].x);
				y = max(y, rat * (temp[i + 1].y - temp[i].y) + temp[i].y);
			}
		}
	}
	return y;
}
double check2(double x,double y)
{
	for (int i = 0; i <= n; i++)
	{
		res[i] = temp[i] - point(x, y);
	}
	return area();
}

double check(double x)
{
	double l2 = get_ymin(x),r2 = get_ymax(x);
	while(abs(r2-l2) > EPS)
	{
		double mid1 = (2*l2+r2)/3,mid2 = (2*r2+l2)/3;
		if(check2(x,mid1) > check2(x,mid2)) r2 = mid2;
		else l2 = mid1;
	}
	return check2(x,l2);
}
int main()
{
	double Mi1 = 10000,Ma1 = -10000,Mi2 = 10000,Ma2 = -10000;
	cin.sync_with_stdio(false);
	cin>>n>>r;
	for(int i = 1;i <= n;i++) 
	{
		cin>>temp[i].x>>temp[i].y;
		Mi1 = min(Mi1,temp[i].x);
		Ma1 = max(Ma1,temp[i].x);
		Mi2 = min(Mi2,temp[i].y);
		Ma2 = max(Ma2,temp[i].y);
	}
	temp[0] = temp[n];
	point center = MassCenter();
	for (int i = 0; i <= n; i++)
		res[i] = temp[i] - center;
/*	double ans = area();
	cerr << center.x << ' ' << center.y << endl;
	printf("%.8f\n", ans);*/
	double l1 = Mi1,r1 = Ma1;
	while(abs(r1 - l1) > EPS)
	{
		double mid1 = (2*l1+r1)/3,mid2 = (2*r1+l1) / 3;
		if(check(mid1) > check(mid2)) r1 = mid2;
		else l1 = mid1;
	}
	printf("%.8lf\n", check(l1));
}