Problem: Example

Input

4 4
0 0
6 0
6 6
0 6


Output

35.759506

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;


struct P {
	double x, y;
	P() {
	}
	P(double _x, double _y) :
			x(_x), y(_y) {
	}
	P operator+(const P&p) const {
		return P(x + p.x, y + p.y);
	}
	P operator-(const P&p) const {
		return P(x - p.x, y - p.y);
	}
	P operator*(double d) const {
		return P(x * d, y * d);
	}
	P operator/(double d) const {
		return P(x / d, y / d);
	}
	double det(const P&p) const {
		return x * p.y - y * p.x;
	}
	double dot(const P&p) const {
		return x * p.x + y * p.y;
	}
	double alpha() const {
		return atan2(y, x);
	}
	P rot90() const {
		return P(-y, x);
	}
	void read() {
		scanf("%lf%lf", &x, &y);
	}
	void write() const {
		printf("(%lf,%lf)", x, y);
	}
	double abs() {
		return sqrt(abs2());
	}
	double abs2() {
		return x * x + y * y;
	}
	P unit() {
		return *this / abs();
	}
};

#define cross(p1,p2,p3) ((p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y))

const double EPS = 1e-8; //you should change it according to problem, nevertheless, it mustn't be a constant value some times.
inline int sign(double a) {
	return a < -EPS ? -1 : a > EPS;
}

#define crossOp(p1,p2,p3) (sign(cross(p1,p2,p3)))

P isSS(P p1, P p2, P q1, P q2) {
	double a1 = cross(q1,q2,p1), a2 = -cross(q1,q2,p2);
	return (p1 * a2 + p2 * a1) / (a1 + a2);
}

int n;

double x[12],y[12],r;

bool onLine(P p, P q, P x){
	return (x-p).dot(x-q) <= EPS;
}

vector<P> isCS(P c,double r,P p, P q){
	double d = cross(q,p,c) / (p-q).abs();
	vector<P> ret;

	if(d>=r+EPS)
		return ret;

	P dir = (q-p).rot90();
	P pq = (p-q);
	pq = pq/pq.abs();

	dir = dir / dir.abs();

	P mid = c + dir * d;

	double h = sqrt(max(r*r-d*d,0.0));
	if(onLine(p,q,mid + pq*h))
		ret.push_back(mid + pq*h);
	if(onLine(p,q,mid - pq*h))
		ret.push_back(mid - pq*h);
	return ret;
}

double rad(P p,P q){
	return atan2(p.det(q),p.dot(q));
}

double calc(P p, P q){
	bool inp = p.abs2() <= r*r;
	bool inq = q.abs2() <= r*r;
	if(inp && inq){
		return p.det(q)/2;
	}
	if(inp && !inq){
		return -calc(q,p);
	}
	vector<P> is = isCS(P(0,0),r,p,q);
	if(!inp && inq){
		P m = is[0];
		return r*r*rad(p,m)/2 + m.det(q)/2;
	}

	if(!inp && !inq){
		if(is.empty())
			return r*r*rad(p,q)/2;
		return r*r*(rad(p,is[0]) + rad(is[1],q))/2 + is[0].det(is[1])/2;
	}
}

double calcArea(double cx,double cy){
	P ps[12];
	rep(i,n) ps[i].x=x[i]-cx,ps[i].y=y[i]-cy;
	ps[n] = ps[0];

	double area = 0;

	rep(i,n){
		P p=ps[i],q=ps[i+1];
		area += calc(p,q);
	}

	//cout<<area<<endl;

	return area;
}

double ffy(double x){
	double l = 1e100,r=-1e100;

	P ps[12];
	rep(i,n) ps[i].x=::x[i], ps[i].y=y[i];

	ps[n] = ps[0];

	rep(i,n){
		P p = ps[i], q = ps[i+1];
		if(p.x > q.x)
			swap(p,q);

		if(p.x<=x+EPS && x<=q.x+EPS){
			double iy;
			if(p.y==q.y)
				iy = p.y;
			else
				iy = p.y + (q.y - p.y) * (x-p.x) / (q.x-p.x);
			l = min(l,iy);
			r = max(r,iy);
		}
	}

	rep(it,100){
		double ll=(l*2+r)/3,rr=(l+r*2)/3;
		if(calcArea(x,ll)>calcArea(x,rr))
			r=rr;
		else
			l=ll;
	}
	return calcArea(x,l);
}

double ffx(){
	double l=*min_element(x,x+n),r=*max_element(x,x+n);

	rep(it,100){
		double ll=(l*2+r)/3,rr=(l+r*2)/3;
		if(ffy(ll)>ffy(rr))
			r=rr;
		else
			l=ll;
	}
	return ffy(l);
}

int main(){
	cin>>n>>r;
	rep(i,n) cin>>x[i]>>y[i];

	printf("%0.10lf\n",ffx());
}