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;
#define SZ(a) int((a).size())
#define mp make_pair
#define pb push_back
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef long long LL;
typedef unsigned long long ULL;
const LL mod=1e9+7;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
const double EPS=1e-6;
inline void read(LL& x){int f=1;char c;while(((c=getchar())<'0'||c>'9')&&c!='-');c=='-'?(f=-1,x=0):(x=c-'0');while((c=getchar())>='0'&&c<='9')x=x*10+c-'0';x*=f;}
inline void read(int& x){LL t;read(t);x=t;}
/*----------------------精度控制--------------------------*/
const double eps=1e-7;
//1:>0 0:=0 -1:<0
int dcmp(double x){
    if(fabs(x)<eps) return 0;
    return x<0?-1:1;
}
/*------------------点、???体-------------------*/
struct Point{
    double x,y;
    Point(double x=0.0,double y=0.0):x(x),y(y){}
    void Read(){ scanf("%lf%lf",&x,&y); }
    void Write(){ printf("%.10f %.10f\n",x,y); }
    bool operator<(const Point &b) const{//水平序
        return !dcmp(x-b.x)? y<b.y:x<b.x;
    }
    /*friend bool operator<(CPoint a,CPoint b){//?角排序
        double tmp=cross(Pts[0],a,b);
        if(!dcmp(tmp)) return dist(Pts[0],a)<dist(Pts[0],b);
        return tmp>0;
    }*/
};
//a->b
struct Line{
    Point a,b;
    Line(Point a,Point b):a(a),b(b){}
    Line(){}
    void Read(){ a.Read(); b.Read(); }
    void Write(){ a.Write(); b.Write(); }
};
/*---------------------点、?相?----------------------*/
Point operator +(Point a,Point b){ return Point(a.x+b.x,a.y+b.y); }
Point operator -(Point a,Point b){ return Point(a.x-b.x,a.y-b.y); }
Point operator *(Point a,double k){ return Point(k*a.x,k*a.y); }
Point operator *(double k,Point a){ return Point(k*a.x,k*a.y); }
double operator *(Point a,Point b){ return a.x*b.x+a.y*b.y; }
Point operator /(Point a,double k){ return Point(a.x/k,a.y/k); }
double operator ^(Point a,Point b){ return a.x*b.y-a.y*b.x; }
double cross(Point a,Point b){ return a.x*b.y-a.y*b.x; }
double cross(Point a,Point b,Point c){ return cross(b-a,c-a); }
double dot(Point a,Point b){ return a.x*b.x+a.y*b.y; }
double dot(Point a,Point b,Point c){ return dot(b-a,c-a); }
double length(Point p){ return sqrt(p*p); }
Point unit(Point p){ return 1.0/length(p)*p; }
//求p在n方向上投影?度
double project(Point p,Point n){ return p*unit(n); }
double area(Point a,Point b){ return a^b*0.5; }
double distPP(Point p,Point q){ return length(p-q); }
double distPL(Point p,Line l){ return fabs((p-l.a)^(p-l.b))/length(l.a-l.b); }
double distPS(Point p,Line s){
    if(dcmp(dot(s.b-s.a,p-s.a))<0) return length(p-s.a);
    if(dcmp(dot(s.a-s.b,p-s.b))<0) return length(p-s.b);
    return distPL(p,s);
}
//b?a逆??旋?alpha后得到的点
Point rotateP(Point a,Point b,double alpha){
    Point p=b-a;
    return Point(a.x+p.x*cos(alpha)-p.y*sin(alpha),a.y+p.x*sin(alpha)+p.y*cos(alpha));
}
//b?a逆??旋?alpha后得到的向量
Point rotateV(Point a,Point b,double alpha){
    Point p=b-a;
    return unit(Point(p.x*cos(alpha)-p.y*sin(alpha),p.x*sin(alpha)+p.y*cos(alpha)));
}
//0:online 1:left -1:right
int sideOfL(Point p,Line l){
    double res=(p-l.a)^(p-l.b);
    return dcmp(res);
}
//求?p的l的垂?
Line vertical(Point p,Line l){
    return Line(p,p+rotateV(l.b,l.a,PI/2));
}
//垂足
Point root(Point p,Line l){
    return l.a+project(p-l.a,l.b-l.a)*unit(l.b-l.a);
}
//?向量?角
double angleVV(Point a,Point b){ return acos(project(a,b)/length(a)); }
//?直??角
double angleLL(Line l,Line m){
    return acos(fabs(project(l.b-l.a,m.b-m.a)/length(l.b-l.a)));
}
//判断点p是否在?段ab上
bool PointOnS(Point p,Line l){
    return !dcmp(cross(p-l.a,l.b-l.a))&&dcmp((p-l.a)*(p-l.b))<=0;
}
//求直?交点
Point getCrossLL(Line l,Line m){
    double t=cross(m.b-m.a,l.a-m.a)/cross(l.b-l.a,m.b-m.a);
    return l.a+(l.b-l.a)*t;
}
//判断?段是否相交
bool crossSS(Line l,Line m){
    return sideOfL(l.a,m)*sideOfL(l.b,m)<=0&&sideOfL(m.a,l)*sideOfL(m.b,l)<=0;
}
/*----------------------多?形相?--------------------------*/
//0:outside 1:inside 2:online
int PointInPoly(Point t,Point *p,int n){
    int num=0,d1,d2,k;
    p[n]=p[0];
    for(int i=0;i<n;i++){
        if(PointOnS(t,Line(p[i],p[i+1]))) return 2;
        k=dcmp(cross(p[i],p[i+1],t));
        d1=dcmp(p[i].y-t.y);
        d2=dcmp(p[i+1].y-t.y);
        if(k>0&&d1<=0&&d2>0) num++;
        if(k<0&&d2<=0&&d1>0) num--;
    }
    return num!=0;
}
//clockwise:>0 anticlockwise:<0
double PolyArea(Point *p,int n){
    double pa=0.0;p[n]=p[0];
    for(int i=0;i<n;i++) pa+=area(p[i],p[i+1]);
    return pa;
}
//求多?形周?
double PolyPerimeter(Point *p,int n){
    double pp=0.0;p[n]=p[0];
    for(int i=0;i<n-1;i++) pp+=distPP(p[i],p[i+1]);
    return pp;
}
//求多?形重心
Point PolyCore(Point *p,int n){
    double pa=PolyArea(p,n);
    if(!dcmp(pa)) return Point(0,0);
    Point ans(0,0);p[n]=p[0];
    for(int i=0;i<n;i++) ans=ans+(p[i]+p[i+1])*cross(p[i],p[i+1]);
    return ans/pa/6;
}
/*----------------------凸包----------------------------*/
//Graham-scan st:anticlockwise
//<=:strict <:Non-strict
int Graham(Point *p,Point *st,int n){
    if(n<3) return 0;
    sort(p,p+n);
    int m=0;
    for(int i=0;i<n;i++){
        while(m>1&&dcmp(cross(st[m-2],st[m-1],p[i]))<0) m--;
        st[m++]=p[i];
    }
    int k=m;
    for(int i=n-2;i>=0;i--){
        while(m>k&&dcmp(cross(st[m-2],st[m-1],p[i])<0)) m--;
        st[m++]=p[i];
    }
    return m-1;
}
//clockwise:> anticlockwise:<
double CHDiameter(Point *p,int n,Line &l){
    double maxd=0.0;
    if(n<=1){
        l.a=l.b=p[0];
        return maxd;
    }
    for(int i=0,j=1;i<n;i++){
        while(cross(p[i],p[(i+1)%n],p[j])
              >cross(p[i],p[(i+1)%n],p[(j+1)%n])){
            j=(j+1)%n;
        }
        double d=distPP(p[i],p[j]);
        if(dcmp(d-maxd)>=0){
            maxd=d;
            l.a=p[i];
            l.b=p[j];
        }
        d=distPP(p[(i+1)%n],p[(j+1)%n]);
        if(dcmp(d-maxd)>=0){
            maxd=d;
            l.a=p[i];
            l.b=p[j];
        }
    }
    return maxd;
}
bool PointInCH(Point *p,int n,Point a){
    int l=0,r=n-1,m,res=-1;
    bool fg=false;
    int pos;
    double flag[2];
    while(l<=r){
        m=(l+r)/2;
        flag[0]=cross(p[0]-a,p[0]-p[m]);
        if(!dcmp(flag[0])){
            fg=true;
            pos=m;
            break;
        }
        flag[1]=cross(p[0]-a,p[0]-p[m+1]);
        if(!dcmp(flag[1])){
            fg=true;
            pos=m+1;
            break;
        }
        if(dcmp(flag[0])*dcmp(flag[1])<0){
            res=m;
            break;
        }
        if(dcmp(flag[0])<0&&dcmp(flag[1])<0) l=m+1;
        else r=m-1;
    }
    if(fg){
        if(dcmp((p[0]-a)*(p[pos]-a))<=0) return true;
        return false;
    }
    if(res==-1) return false;
    return dcmp(cross(p[m]-a,p[m]-p[m+1]))<=0;
}


/*---------------------整点多?形---------------------------*/
int gcd(int a,int b){
    return b==0?a :gcd(b,a%b);
}
//整点多?形?界整点数
int Border_Int_Point_Num(Point *Pts,int n){
    int num=gcd(abs(int(Pts[0].x-Pts[n-1].x)),abs(int(Pts[0].y-Pts[n-1].y)));;
    for(int i=0;i<n-1;i++){
        num+=gcd(abs(int(Pts[i+1].x-Pts[i].x)),abs(int(Pts[i+1].y-Pts[i].y)));
    }
    return num;
}
//整点多?形内部整点数
int Inside_Int_Point_Num(Point *Pts,int n){
    return abs(int(PolyArea(Pts,n)))+1-Border_Int_Point_Num(Pts,n)/2;
}
/*-----------------------------半平面交-------------------------------*/
//有方向的直?
//p->p+v
struct Vector{
    Point p,v;
    double ang;
    Vector(Point p,Point v):p(p),v(v){
        ang=atan2(v.y,v.x);
    }
    Vector(){}
    bool operator<(const Vector &l) const{
        return ang<l.ang;
    }
};
//判断点p是否在直?L左?
bool onLeft(Vector L,Point p){
    return cross(L.v,p-L.p)>0;
}
//得到a与b?直?的交点
Point getCrossVV(Vector a,Vector b){
    Point u=a.p-b.p;
    double t=cross(b.v,u)/cross(a.v,b.v);
    return a.p+a.v*t;
}
//所有直?左半平面的交
int HPCross(Vector *L,int n,Point *poly){
    sort(L,L+n);
    int f=0,l=0;
    Point *p=new Point[n];
    Vector *q=new Vector[n];
    q[0]=L[0];
    for(int i=1;i<n;i++){
        while(f<l&&!onLeft(L[i],p[l-1])) l--;
        while(f<l&&!onLeft(L[i],p[f])) f++;
        q[++l]=L[i];
        if(!dcmp(cross(q[l].v,q[l-1].v))){
            l--;
            if(onLeft(q[l],L[i].p)) q[l]=L[i];
        }
        if(f<l) p[l-1]=getCrossVV(q[l-1],q[l]);
    }
    while(f<l&&!onLeft(q[f],p[l-1])) l--;
    if(l-f<=1) return 0;
    p[l]=getCrossVV(q[l],q[f]);
    int m=0;
    for(int i=f;i<=l;i++) poly[m++]=p[i];
    return m;
}
//向内??r
#define maxn 100005
Vector l[maxn];
bool retract(Vector *L,int n,double r,Point *poly){
    for(int i=0;i<n;i++){
        Point v=rotateV(L[i].p,L[i].p+L[i].v,PI/2);
        l[i]=Vector(L[i].p+r*v,L[i].v);
    }
    int cnt=HPCross(l,n,poly);
    return cnt;
}
/*---------------------三角形相?---------------------------*/
//三角形重心
//到三?点距?的平方和最小的点
//到三?距?之?最大的点
Point TCore(Point a,Point b,Point c){
    return (a+b+c)/3;
}
//三角形外心
Point TCircum(Point a,Point b,Point c){
    Point cp;
    double a1=b.x-a.x;
    double b1=b.y-a.y;
    double a2=c.x-a.x;
    double b2=c.y-a.y;
    double c1=(a1*a1+b1*b1)/2;
    double c2=(a2*a2+b2*b2)/2;
    double d=a1*b2-a2*b1;
    cp.x=a.x+(c1*b2-c2*b1)/d;
    cp.y=a.y+(a1*c2-a2*c1)/d;
    return cp;
}
//三角形垂心
Point TOrtho(Point a,Point b,Point c){
    return TCore(a,b,c)*3.0-TCircum(a,b,c)*2.0;
}
//三角形内心
Point TInner(Point a,Point b,Point c){
    Point cp;
    double la=distPP(b,c),lb=distPP(c,a),lc=distPP(a,b);
    cp.x=(la*a.x+lb*b.x+lc*c.x)/(la+lb+lc);
    cp.y=(la*a.y+lb*b.y+lc*c.y)/(la+lb+lc);
    return cp;
}
//求三角形面?
double TArea(Point a,Point b,Point c){
    return fabs(cross(a,b,c))/2;
}
/*-----------------------?相?-------------------------*/
struct Circle{
    Point o; double r;
    Circle(Point o,double r):o(o),r(r){}
    Circle(){}
    void Read(){ o.Read(); scanf("%lf",&r); }
    double area(){ return PI*r*r; }
};
//求??面?交
double getAreaCC(Circle a,Circle b){
    double d=(a.o.x-b.o.x)*(a.o.x-b.o.x)+(a.o.y-b.o.y)*(a.o.y-b.o.y);
    if(d<=(a.r-b.r)*(a.r-b.r)){
        return min(a.r,b.r)*min(a.r,b.r)*PI;
    }else if(d>(a.r-b.r)*(a.r-b.r)&&d<(a.r+b.r)*(a.r+b.r)){
        double m1=(a.r*a.r+d-b.r*b.r)/(2*a.r*sqrt(d));
        double m2=(b.r*b.r+d-a.r*a.r)/(2*b.r*sqrt(d));
        double s1=acos(m1)*a.r*a.r;
        double s2=acos(m2)*b.r*b.r;
        double s3=sqrt(d)*a.r*sin(acos(m1));
        return s1+s2-s3;
    }
    return 0.0;
}
//求??交点，先判断是否有交点
Point rotatePCS(Point p,double c,double s){
    return Point(p.x*c-p.y*s,p.x*s+p.y*c);
}
pair<Point,Point> getcrossCC(Circle a,Circle b){
    double d=length(a.o-b.o);
    double cost=(a.r*a.r+d*d-b.r*b.r)/(2*a.r*d);
    double sint=sqrt(1.0-cost*cost);
    Point v=(b.o-a.o)/d*a.r;
    return mp(a.o+rotatePCS(v,cost,-sint),a.o+rotatePCS(v,cost,sint));
}
int getCrossCL(Circle c,Line l,Point *cl){
    int fg=dcmp(distPL(c.o,l)-c.r);
    int cnt=0;
    if(!fg) cl[cnt++]=root(c.o,l);
    else if(fg==-1){
        Point rt=root(c.o,l);
        double r=sqrt(c.r*c.r-(c.o-rt)*(c.o-rt));
        cl[cnt++]=rt+r*unit(l.b-l.a);
        cl[cnt++]=rt-r*unit(l.b-l.a);
    }
    return cnt;
}

double rad(Point a,Point b,Point p){
    return fabs(atan2(fabs(cross(a-p,b-p)),(a-p)*(b-p)));
}
Point lineprog(Line l,Point p){
    return l.a+(((l.b-l.a)*((l.b-l.a)*(p-l.a)))/((l.b-l.a)*(l.b-l.a)));
}
int relation(Point b,Circle c){
    double d=distPP(b,c.o);
    if(dcmp(d-c.r)<0) return 2;
    if(!dcmp(d-c.r)) return 1;
    return 0;
}
int getCrossCL(Circle c,Line l,Point &p1,Point &p2){
    double dx=distPL(c.o,l);
    if(dcmp(dx-c.r)>0) return 0;
    Point a=lineprog(l,c.o);
    double d=distPL(c.o,l);
    d=sqrt(c.r*c.r-d*d);
    if(!dcmp(d)){
        p1=p2=a;
        return 1;
    }
    Point s=unit(l.b-l.a);
    p1=a+s*d;
    p2=a-s*d;
    return 2;
}
double getAreaTC(Point a,Point b,Circle c){
    Point q[5];
    int len=0;
    q[len++]=a;
    Line l(a,b);
    Point p1,p2;
    if(getCrossCL(c,l,q[1],q[2])==2){
        if(dcmp((a-q[1])*(b-q[1]))<0) q[len++]=q[1];
        if(dcmp((a-q[2])*(b-q[2]))<0) q[len++]=q[2];
    }
    q[len++]=b;
    if(len==4&&dcmp((q[0]-q[1])*(q[2]-q[1]))>0) swap(q[1],q[2]);
    double res=0.0;
    for(int i=0;i<len-1;i++){
        if(!relation(q[i],c)||!relation(q[i+1],c)){
            double arg=rad(q[i],q[i+1],c.o);
            res+=c.r*c.r*arg/2.0;
        }else res+=fabs(cross(q[i]-c.o,q[i+1]-c.o))/2.0;
    }
    return res;
}
double getAreaPC(Point *Pts,int n,Circle c){
    double apc=0.0;
    for(int i=0;i<n;i++){
        int s=dcmp(cross(Pts[i]-c.o,Pts[i+1]-c.o));
        if(!!s) apc+=getAreaTC(Pts[i],Pts[i+1],c)*s;
    }
    return fabs(apc);
}

/*----------------------三?点、?基本函数-----------------------------*/
struct Point3{
    double x,y,z;
    Point3(double x,double y,double z):x(x),y(y),z(z){}
    Point3(){}
    void Read(){ scanf("%lf%lf%lf",&x,&y,&z); }
};
struct Line3{
    Point3 a,b;
    Line3(Point3 a,Point3 b):a(a),b(b){}
    Line3(){}
    void Read(){ a.Read(); b.Read(); }
};
Point3 operator +(Point3 a,Point3 b){ return Point3(a.x+b.x,a.y+b.y,a.z+b.z); }
Point3 operator -(Point3 a,Point3 b){ return Point3(a.x-b.x,a.y-b.y,a.z-b.z); }
double operator *(Point3 a,Point3 b){ return a.x*b.x+a.y*b.y+a.z*b.z; }
Point3 operator *(Point3 a,double k){ return Point3(a.x*k,a.y*k,a.z*k); }
Point3 operator *(double k,Point3 a){ return Point3(a.x*k,a.y*k,a.z*k); }
Point3 operator /(Point3 a,double k){ return Point3(a.x/k,a.y/k,a.z/k); }
double length(Point3 a){ return sqrt(a.x*a.x+a.y*a.y+a.z*a.z); }
Point3 unit(Point3 a){ return a/length(a); }
double dot(Point3 a,Point3 b){ return a.x*b.x+a.y*b.y+a.z*b.z; }
Point3 cross(Point3 a,Point3 b){
    return Point3(a.y*b.z-a.z*b.y,a.z*b.x-a.x*b.z,a.x*b.y-a.y*b.x);
}
//混合?
double Mix(Point3 a,Point3 b,Point3 c){ return dot(a,cross(b,c)); }
//?点距?
double dist(const Point3 &a,const Point3 &b){ return length(a-b); }
/*---------------------------------体?-------------------------------------*/
//四面体体?
double volume(double l,double n,double a,double m,double b,double c){
    double x,y;
    x=4*a*a*b*b*c*c-a*a*(b*b+c*c-m*m)*(b*b+c*c-m*m)-b*b*(c*c+a*a-n*n)*(c*c+a*a-n*n);
    y=c*c*(a*a+b*b-l*l)*(a*a+b*b-l*l)-(a*a+b*b-l*l)*(b*b+c*c-m*m)*(c*c+a*a-n*n);
    return sqrt(x-y)/12;
}
double volume(Point3 a,Point3 b,Point3 c,Point3 d){ return fabs(Mix(b-a,c-a,d-a)/6); }

#define MAXN 15
Point Pts[MAXN];
int n;
double R,minx,miny,maxx,maxy;
double sanfeny(double x){
    double l=maxy,r=miny;
    Line s=Line(Point(x,0),Point(x,1));
    for(int i=0;i<n;i++){
        Point st=getCrossLL(s,Line(Pts[i],Pts[i+1]));
        if(PointOnS(st,Line(Pts[i],Pts[i+1]))){
            l=min(l,st.y);
            r=max(r,st.y);
        }
    }
    double m1,m2;
    for(int i=0;i<100;i++){
        m1=(l+l+r)/3;
        m2=(l+r+r)/3;
        if(getAreaPC(Pts,n,Circle(Point(x,m1),R))<getAreaPC(Pts,n,Circle(Point(x,m2),R))){
            l=m1;
        }else{
            r=m2;
        }
    }
    return getAreaPC(Pts,n,Circle(Point(x,l),R));
}
double sanfenx(){
    double l=minx,r=maxx;
    double m1,m2;
    for(int i=0;i<100;i++){
        m1=(l+l+r)/3;
        m2=(l+r+r)/3;
        if(sanfeny(m1)<sanfeny(m2)){
            l=m1;
        }else{
            r=m2;
        }
    }
    return sanfeny(l);
}
int main(){ios_base::sync_with_stdio(0);//cin.tie(0);
    minx=miny=1000;
    maxx=maxy=0;
    cin>>n>>R;
    for(int i=1;i<=n;i++){
        cin>>Pts[n-i].x>>Pts[n-i].y;
        minx=min(minx,Pts[n+1-i].x);
        miny=min(miny,Pts[n+1-i].y);
        maxx=max(maxx,Pts[n+1-i].x);
        maxy=max(maxy,Pts[n+1-i].y);
    }
    Pts[n]=Pts[0];
    double maans=sanfenx();
    cout.setf(ios::fixed);
    cout<<fixed<<setprecision(10)<<maans<<endl;
    return 0;
}
//cout.setf(ios::fixed);
//cout<<fixed<<setprecision(10)<<s<<endl;