Problem: Example

Input

4 4
0 0
6 0
6 6
0 6


Output

35.759506

Solution (in CPP):

Solution:
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>

#include <iostream>
#include <algorithm>

typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef double db;
typedef unsigned char uchar;

using namespace std;

int getint(int x=0) { scanf("%d",&x); return x; }
ll getll(ll x=0) { scanf("%lld", &x); return x; }
double getdb(double x=0) { scanf("%lf",&x); return x; }

// ====================================================1========

const int INF = (1<<30)-1;
const ll LINF = (1L<<62)-1;

const double eps = 1e-10;

struct point;

struct point
{
    db x,y;
    point() : x(0),y(0) { }
    point(db x, db y) : x(x),y(y) { }
    db len() { return sqrt(x*x+y*y); }
    db len2() { return x*x+y*y; }
    point operator()(point b) const { return point(b.x-x, b.y-y); }
    point norm() { double l = len(); return point(x/l, y/l); }
    void out(const char* s = "") { printf("(%.2f, %.2f) %s", x, y, s); }
    point operator-() { return point(-x, -y); }
};

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); }
db operator*(point a, point b) { return a.x * b.y - a.y * b.x; }
db operator&(point a, point b){ return a.x * b.x + a.y * b.y; }
point operator*(point a, db f) { return point(a.x * f, a.y * f); }
point operator*(db f, point a) { return point(a.x * f, a.y * f); }
point operator/(point a, db f) { return point(a.x / f, a.y / f); }
db Area(point a, point b, point c) { return abs(c(a)*c(b)*0.5); }
db Angle(point a, point b) { return acos((a&b)/a.len()/b.len()); }
db DistP2L(point c, point a, point b) { return Area(a,b,c) * 2.0 / a(b).len(); }
db ArcArea(db r, db angle) { return angle * r * r / 2.0; }
db ArcArea(db r, point c, point a, point b) { return ArcArea(r, Angle(c(a), c(b))); }
point rot90(point c) { return point(-c.y, c.x); }

db IntArea(db r, point c, point a,point b)
{
    if( c(a).len() < eps ||
        c(b).len() < eps ||
        a(b).len() < eps)
        return 0;
    
    bool ain = c(a).len() < r;
    bool bin = c(b).len() < r;
    
    if(ain && bin)
    {
        //printf("!!!");
        return abs(c(a) * c(b) * 0.5);
    }
    
    db d = DistP2L(c, a, b);
    //printf("d:%.8f ", d);
    
    if(!ain && !bin)
    {
        //printf("xx");
        if(d < r) // line intersect!
        {
            db m = sqrt(r*r-d*d);
            point dir = rot90(a(b)).norm() * d;
            if(DistP2L(c + dir, a, b) > eps)
                dir = - dir;
            point ita = c + dir + a(b).norm() * m;
            point itb = c + dir + b(a).norm() * m;
            
            if((ita(a) & ita(b)) >= 0) // two points are on the same side.
            {
                //printf("^");
                return ArcArea(r, c, a, b);
            }
            
            //printf("-");
            db Tar = m * d;
            if(a(ita).len() > a(itb).len()) swap(ita, itb);
            db Aar = ArcArea(r, c, a, ita);
            db Bar = ArcArea(r, c, b, itb);
            // a.out(); b.out("\n");
            // ita.out(); itb.out("\n");
            // a(ita).out(); a(itb).out("\n");
            // c(a).out(); c(itb).out(); c(ita).out("\n");
            // printf("angle: %.6f\n", Angle(c(a), c(ita)));
            // printf(" r:%.2f d:%.2f m:%.2f t:%.2f a:%.2f b:%.2f\n", r, d, m, Tar, Aar, Bar);
            return Tar + Aar + Bar;
        }
        else // line not intersect.
        {
            //printf(".");
            return ArcArea(r, c, a, b);
        }
    }
    
    //printf("x. ");
    if(!ain && bin) swap(a, b);
    
    point dir = rot90(a(b)).norm() * d;
    if(DistP2L(c + dir, a, b) > eps) dir = - dir;
    db m = sqrt(r*r-d*d);
    point ita = c + dir + a(b).norm() * m;
    return a(ita).len() * d * 0.5 + ArcArea(r, c, b, ita);
}

int n;
db r;

point p[50];

db GetIntArea(point c)
{
    db res = 0.0;
    for(int i=1; i<=n; i++)
    {
        point a = p[i];
        point b = p[i-1];
        if(c(a).len() <= eps || c(b).len() <= eps) continue;
        if(a(c) * c(b) > eps) // positive triangle.
            res += IntArea(r, c, a, b);
        else if(a(c) * c(b) < eps)
            res -= IntArea(r, c, a, b);
        //printf("(%.2f, %.2f)-(%.2f, %.2f) %.8f ", a.x, a.y, b.x, b.y, IntArea(r, c, a, b));
        //printf("%.8f\n", res);
    }
    //printf("%.2f\n", res);
    return res;
}

double randdb() { return (db)rand() / RAND_MAX; }

int main()
{
    n = getint();
    r = getint();
    for(int i=1; i<=n; i++)
    {
        p[i].x = getint();
        p[i].y = getint();
    }
    p[0] = p[n];
    
    // Sim Anealling.
    
    srand(12512);
    db Tbegin = 1e2;
    db Tend = 1e-6;
    db T = Tbegin;
    db rate = 0.99995;
    int cnt = 0;
    int tcnt = 0;
    point mvbase = point(0.01, 0.01);
    point curp = p[1];
    db curmax = GetIntArea(curp);
    while(T >= Tend)
    {
        point nxtp = curp + point(
            (randdb() - 0.5) * 2.0 * mvbase.x * T,
            (randdb() - 0.5) * 2.0 * mvbase.y * T);
        db v = GetIntArea(nxtp);
        db dist = v - curmax;
        //nxtp.out(""); printf("v:%.4f dist:%.4f T:%.6f, p:%.4f\n", v, dist, T, exp(dist / T));
        if(dist > eps || (dist < -eps && randdb() > exp(dist / T))
        )
        {
            curmax = v;
            curp = nxtp;
            tcnt++;
        }
        T *= rate;
        //T -= 1e-6;
        cnt++;
    }
    
    //printf("SA count:%d, transfer count:%d\n", cnt, tcnt);
    printf("%.6f\n", curmax);
    
    // printf("%.8f\n", IntArea(1, {0, 0}, {1, 0}, {0, 1})); // 0.5 .
    // printf("%.8f\n", IntArea(1, {0, 0}, {2, 0}, {0, 2}));
    // printf("%.8f\n", IntArea(1, {0, 0}, {1.00000001, 0}, {0, 0.5}));
    // printf("res, %.8f\n", IntArea(1, {5.44, -0.62}, {0, 0}, {100, 1}));
    // printf("res, %.8f\n", IntArea(1, {5.44, -0.62}, {100, 1}, {99, 1}));
    // printf("res, %.8f\n", IntArea(1, {5.44, -0.62}, {99, 1}, {0, 0}));
    // printf("res, %.8f\n", IntArea(1, {98.21, 0.39}, {0, 0}, {100, 1}));
    // printf("res, %.8f\n", IntArea(1, {98.21, 0.39}, {100, 1}, {99, 1}));
    // printf("res, %.8f\n", IntArea(1, {98.21, 0.39}, {99, 1}, {0, 0}));
    
    return 0;
}