Problem: Example

Input

4 4
0 0
6 0
6 6
0 6


Output

35.759506

Solution (in CPP):

Solution:
#include <iostream>
#include <complex>
#include <vector>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <map>
 
using namespace std;
#define x1 jkflwjjkfjekjfe
#define x2 fwekwfefekfje
 
int iter = log(100 * 100 * 10000) / log(3) + 20;
typedef complex<double> P;
struct L{
	P a,b;
};
vector<double> ax,ay;
vector<L> ls;
double R,cx,cy;
 
bool eq(double a,double b){
	return fabs(a-b) < 1e-7;
}
bool eq2(double a,double b){
	return fabs(a-b) < 1e-8;
}
 
pair<double,double> seg(double y){
	double x1 = +1e5;
	double x2 = -1e5;
	for( auto &&l : ls){
		if( eq(l.a.imag(),y) ){
			x1 = min(x1,l.a.real());
			x2 = max(x2,l.a.real());
		}
		if( eq(l.b.imag(),y) ){
			x1 = min(x1,l.b.real());
			x2 = max(x2,l.b.real());
		}
		if( l.a.imag() + 1e-7 < y and y < l.b.imag() - 1e-7 ){
			P v = (l.b - l.a);
			P p = l.a + v * (y-l.a.imag()) / v.imag();
			x1 = min(x1,p.real());
			x2 = max(x2,p.real());  
		}
	}
	return {x1,x2};
}
 
double len(pair<double,double> p){
	if( p.first < p.second ) return p.second - p.first;
	return 0;
}
pair<double,double> merge(const pair<double,double> &a,const pair<double,double> &b){
	return {max(a.first,b.first),min(a.second,b.second)};
}
 
double g(double y){
	if( R - abs(y-cy) < 1e-7 ) return 0;
	// for given y, compute the overlapped length of the circle and the polygon.
	double t = sqrt(R*R-(cy-y)*(cy-y));
	pair<double,double> circle_seg = {cx-t,cx+t};
	return len(merge(circle_seg,seg(y)));
}
 
double simpson(double l,double r){
	return (r-l)/6*(g(l)+4*g((l+r)/2)+g(r));
}
double integral(double l,double r,int k=5){
	if( l >= r ) return 0;
 
	double m = (l+r) / 2;
	double A = simpson(l,m) + simpson(m,r);
	double B = simpson(l,r);
	if( k<=0 and eq2(A,B) ) return A;
	else return integral(l,m,k-1) + integral(m,r,k-1);
}
 
double f(double x,double y){
	cx = x;
	cy = y;
	double ans = 0;
	for(int i = 0 ; i+1 < ay.size() ; i++){
		ans += integral(max(cy-R,ay[i]),min(cy+R,ay[i+1]));
	}

	return ans;
}
		
double search2(double y){
	double ans = 0;
	double l,r;
 
	tie(l,r) = seg(y);
 
	for(int i = 0 ; i < iter ; i++){
		double a = (2*l+r) / 3;
		double b = (l+2*r) / 3;
		if( f(a,y) < f(b,y) ){
			l = a;
		}else{
			r = b;
		}
	}
	return f(l,y);
}
 
double search1(){
	double ans = 0;
	double l = ay.front(), r = ay.back();
	for(int i = 0 ; i < iter ; i++){
		double a = (2*l+r) / 3;
		double b = (l+2*r) / 3;
		if( search2(a) < search2(b) ){
			l = a;
		}else{
			r = b;
		}
	}
	
	return search2(l);
}
 
int main(){
	int n;
	cin >> n >> R;
	vector<P> g(n+1);
	for(int i = 0 ; i < n ; i++){
		double x,y;
		cin >> x >> y;
		g[i] = P(x,y);
		ax.push_back(x);
		ay.push_back(y);
	}
	g[n] = g[0];
	 
	for(int i = 0 ; i < n ; i++){
		ls.push_back({g[i],g[i+1]});
		if( ls.back().a.imag() > ls.back().b.imag() ) swap(ls.back().a,ls.back().b);
	}

	sort(ax.begin(),ax.end());
	sort(ay.begin(),ay.end());
	ax.erase(unique(ax.begin(),ax.end()),ax.end());
	ay.erase(unique(ay.begin(),ay.end()),ay.end());
	//printf("%.10lf\n",f(0,0));
 	//return 0;
 	
	printf("%.10lf\n",search1());
 
}