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;
typedef complex<double> P;
typedef vector< P > vecp;

struct S{
  P p,q;
  S(P p,P q) : p(p),q(q) {}  
};

struct C{
  P p;  double r;
  C(P p,double r):p(p),r(r){}
  C(double x,double y,double rr){
    p=P(x,y);
    r=rr;
  }
};

double eps=1e-8,  PI=acos(-1),  PI2=PI*2.0;

bool eq(double a,double b){return (b-a<eps&&a-b<eps);}
bool eq(P a,P b){return (abs(a-b)<eps);}
double Sqrt(double x){  return ( x<0 ? 0.0 : sqrt(x) ); }
double dot(P a,P b){return real(b*conj(a));}
double cross(P a,P b){return imag(b*conj(a));}

double dist(P a,P b,P c){
  if(dot(b-a,c-a)<0)return abs(c-a);
  if(dot(a-b,c-b)<0)return abs(c-b);
  return abs(cross(b-a,c-a))/abs(b-a);
}

P project(P a,P b,P c){  b-=a; c-=a; return a+b*real(c/b); }

double getTime(P a,P b){
  assert( eq(cross(a,b),0) );
  return ( dot(a,b) < 0 ? -1.0 : 1.0 ) * abs(b);
}

bool onSegment(P a,P b,P p){
  return eq( abs(a-b) , abs(a-p)+abs(b-p) );
}

P getCrossPoint(P a,P b,P c,P d){
  a-=d;b-=d;c-=d;
  return d+a+(b-a)*imag(a/c)/imag(a/c-b/c);
}

double getArg(P a,P b){  return arg(b*conj(a)); }

vecp getCrossPoint(C c,P a,P b){
  vecp res;
  P base=b-a,  target=project(a,b,c.p);
  double length=abs(base), h=abs(c.p-target);
  if(c.r+eps<h)return res;
  double w=Sqrt(c.r*c.r-h*h);
  double L=getTime(base,target-a)-w, R=L+w*2.0;
  base/=length;
  if( -eps<L && L<length+eps )res.push_back(a+base*L);
  if( eq(L,R) )return res;
  if( -eps<R && R<length+eps )res.push_back(a+base*R);
  return res;
}

vecp getCrossPoint(C a,S b, bool debug=false){
  vecp res;
  P base=b.q-b.p,  target=project(b.p,b.q,a.p);
  double length=abs(base), h=abs(a.p-target);
  if(a.r+eps<h)return res;
  double w=Sqrt(a.r*a.r-h*h);
  double L=getTime(base,target-b.p)-w,  R=L+w*2.0;
  base/=length;  
  if( -eps<L && L< length+eps )res.push_back(b.p+base*L);
  if( eq(L,R) )return res;
  if( -eps<R && R< length+eps )res.push_back(b.p+base*R);
  return res;
}

double getArea(C c,P a,P b){
  P va=c.p-a,  vb=c.p-b;
  double A=abs(va), B=abs(vb);
  double f=cross(va,vb), d=dist(a,b,c.p), res=0;
  if( eq(0, f ) )return 0;
  if(A<c.r+eps&&B<c.r+eps)return f*0.5;
  if(d>c.r-eps)return c.r*c.r*PI*getArg(va,vb)/PI2;
  
  vecp u=getCrossPoint(c, S(a,b) );
  assert( !u.empty() );
  u.insert(u.begin(), a),  u.push_back(b);

  for(int i=0;i+1<(int)u.size();i++) res+=getArea(c,u[i],u[i+1]);
  return res;
}

double getArea(vecp t,C c){
  int n=t.size();
  if(n<3)return 0;
  double res=0;
  for(int i=0;i<n;i++){
    P a=t[i], b=t[(i+1)%n];
    res+=getArea(c,a,b);
  }
  return res;
}

int n;
double cr;
vecp t;

double calc(double gx){
  double left=1e9, right=-1e9;
  for(int i=0;i<(int)t.size();i++){
    P a=t[i];
    P b=t[ (i+1)%n ];
    P k=getCrossPoint( a,b, P(gx,0), P(gx,1) );
    if( onSegment(a,b,k) == false )continue;
    left=min(left,k.imag());
    right=max(right,k.imag());
  }
  
  for(int i=0;i<100;i++){
    double dist=(right-left)/3.0;
    double ml=left+dist;
    double mr=right-dist;
    if( getArea(t,C(P(gx,ml),cr)) > getArea(t,C(P(gx,mr),cr))){
      right=mr;
    }else{
      left=ml;
    }
      
  }
  return getArea(t,C(P(gx,left),cr));
}

int main(){
  cin>>n>>cr;
  double left=1e9, right=-1e9;
  
  for(int i=0;i<n;i++){
    double x,y;
    cin>>x>>y;
    t.push_back(P(x,y));
    left=min(left,x);
    right=max(right,x);
  }

  for(int i=0;i<100;i++){
    double dist=(right-left)/3.0;
    double ml=left+dist,mr=right-dist;
    if( calc(ml) > calc(mr) )right=mr;
    else left=ml;
  }
  printf("%.10f\n", calc(left) );
  return 0;
}