Revise paste fak | CCCPaste

//Слава Україні, Героям слава

#include <bits/stdc++.h>

using namespace std;

#define st first
#define nd second
#define pb push_back
#define cl(x,v) memset((x), (v), sizeof(x))
#define db(x) cerr << #x << " == " << x << endl
#define dbs(x) cerr << x << endl
#define _ << ", " <<

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
typedef vector<int> vi;
typedef vector <vi> vii;

const ld EPS = 1e-7, PI = acos(-1.);
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f, MOD = 1e9 + 7;
const int N = 1e5 + 5;

//for big coordinates change to long long
typedef long double type;

/* The functions above are for:
    ge => greater or equal
    le => lesser or equal
    eq => equal
    sign => sign of a number (+ or -)
*/
bool ge(type x, type y) { return x > y - EPS; }
bool le(type x, type y) { return x - EPS < y; }
bool eq(type x, type y) { return ge(x, y) and le(x, y); }
int sign(type x) { return ge(x, 0) - le(x, 0); }

struct point {
    type x, y;

point() : x(0), y(0) {}
    point(type _x, type _y) : x(_x), y(_y) {}

point operator -() { return point(-x, -y); }
    point operator +(point p) { return point(x + p.x, y + p.y); }
    point operator -(point p) { return point(x - p.x, y - p.y); }

point operator *(type k) { return point(x * k, y * k); }
    point operator /(type k) { return point(x / k, y / k); }

//inner product
    type operator *(point p) { return x * p.x + y * p.y; }
    //cross product
    type operator %(point p) { return x * p.y - y * p.x; }

bool operator ==(const point& p) const { return x == p.x and y == p.y; }
    bool operator !=(const point& p) const { return x != p.x or y != p.y; }
    bool operator <(const point& p) const { return (x < p.x) or (x == p.x and y < p.y); }

// 0 => same direction
    // 1 => other is on the left 
    //-1 => other is on the right 
    int dir(point origin, point other) {
        type d = (*this - origin) % (other - origin);
        return ge(d, 0) - le(d, 0);
    }

bool on_seg(point p, point q) {
        if (this->dir(p, q)) return 0;
        return ge(x, min(p.x, q.x)) and le(x, max(p.x, q.x)) and ge(y, min(p.y, q.y)) and le(y, max(p.y, q.y));
    }

ld abs() { return sqrt(x * x + y * y); }
    type abs2() { return x * x + y * y; }
    ld dist(point q) { return (*this - q).abs(); }
    type dist2(point q) { return (*this - q).abs2(); }

ld arg() { return atan2l(y, x); }

// Project point on vector y
    point project(point y) { return y * ((*this * y) / (y * y)); }

// Project point on line generated by points x and y
    point project(point x, point y) { return x + (*this - x).project(y - x); }

ld dist_line(point x, point y) { return dist(project(x, y)); }

ld dist_seg(point x, point y) {
        return project(x, y).on_seg(x, y) ? dist_line(x, y) : min(dist(x), dist(y));
    }

point rotate(ld sin, ld cos) { return point(cos * x - sin * y, sin * x + cos * y); }
    point rotate(ld a) { return rotate(sin(a), cos(a)); }

// rotate around the argument of vector p
    point rotate(point p) { return rotate(p.y / p.abs(), p.x / p.abs()); }

};

int direction(point origin, point p, point other) { return p.dir(origin, other); }

//rotates 90 degrees counter clockwise
point rotate_ccw90(point p) { return point(-p.y, p.x); }
//rotates 90 degrees clockwise
point rotate_cw90(point p) { return point(p.y, -p.x); }

//for reading purposes avoid using * and % operators, use the functions below:
type dot(point p, point q) { return p.x * q.x + p.y * q.y; }
type cross(point p, point q) { return p.x * q.y - p.y * q.x; }

//twice the area of a triangle
type area_2(point a, point b, point c) { return cross(a, b) + cross(b, c) + cross(c, a); }

/*Compares the absolute angle defined by (a1 and b1) vs angle defined by (a2 and b2)
    1  : bigger
    -1 : smaller
    0  : equal
Example:
    angle_less(point(1, 0) , point(0, 1), point(-1, 0), point(-1, -1)) == 1

the angle formed by the two first vectors is 90 degrees
    the angle formed by the two last vectors is 45 degrees
*/
int angle_less(const point& a1, const point& b1, const point& a2, const point& b2) {
    point p1(dot(a1, b1), abs(cross(a1, b1)));
    point p2(dot(a2, b2), abs(cross(a2, b2)));
    if (cross(p1, p2) < 0) return 1;
    if (cross(p1, p2) > 0) return -1;
    return 0;
}

ostream& operator<<(ostream& os, const point& p) {
    os << "(" << p.x << "," << p.y << ")";
    return os;
}

point project_point_line(point c, point a, point b) {
    ld r = dot(b - a, b - a);
    if (fabs(r) < EPS) return a;
    return a + (b - a) * dot(c - a, b - a) / dot(b - a, b - a);
}

point project_point_ray(point c, point a, point b) {
    ld r = dot(b - a, b - a);
    if (fabs(r) < EPS) return a;
    r = dot(c - a, b - a) / r;
    if (le(r, 0)) return a;
    return a + (b - a) * r;
}

point project_point_segment(point c, point a, point b) {
    ld r = dot(b - a, b - a);
    if (fabs(r) < EPS) return a;
    r = dot(c - a, b - a) / r;
    if (le(r, 0)) return a;
    if (ge(r, 1)) return b;
    return a + (b - a) * r;
}

ld distance_point_line(point c, point a, point b) {
    return c.dist2(project_point_line(c, a, b));
}

ld distance_point_ray(point c, point a, point b) {
    return c.dist2(project_point_ray(c, a, b));
}

ld distance_point_segment(point c, point a, point b) {
    return c.dist2(project_point_segment(c, a, b));
}

//not tested
ld distance_point_plane(ld x, ld y, ld z,
    ld a, ld b, ld c, ld d)
{
    return fabs(a * x + b * y + c * z - d) / sqrt(a * a + b * b + c * c);
}

bool lines_parallel(point a, point b, point c, point d) {
    return fabs(cross(b - a, d - c)) < EPS;
}

bool lines_collinear(point a, point b, point c, point d) {
    return lines_parallel(a, b, c, d)
        && fabs(cross(a - b, a - c)) < EPS
        && fabs(cross(c - d, c - a)) < EPS;
}

point lines_intersect(point p, point q, point a, point b) {
    point r = q - p, s = b - a, c(p % q, a % b);
    if (eq(r % s, 0)) return point(LINF, LINF);
    return point(point(r.x, s.x) % c, point(r.y, s.y) % c) / (r % s);
}

//be careful: test line_line_intersection before using this function
point compute_line_intersection(point a, point b, point c, point d) {
    b = b - a; d = c - d; c = c - a;
    assert(dot(b, b) > EPS && dot(d, d) > EPS);
    return a + b * cross(c, d) / cross(b, d);
}

bool line_line_intersect(point a, point b, point c, point d) {
    if (!lines_parallel(a, b, c, d)) return true;
    if (lines_collinear(a, b, c, d)) return true;
    return false;
}

//rays in direction a -> b, c -> d
bool ray_ray_intersect(point a, point b, point c, point d) {
    if (a.dist2(c) < EPS || a.dist2(d) < EPS ||
        b.dist2(c) < EPS || b.dist2(d) < EPS) return true;
    if (lines_collinear(a, b, c, d)) {
        if (ge(dot(b - a, d - c), 0)) return true;
        if (ge(dot(a - c, d - c), 0)) return true;
        return false;
    }
    if (!line_line_intersect(a, b, c, d)) return false;
    point inters = lines_intersect(a, b, c, d);
    if (ge(dot(inters - c, d - c), 0) && ge(dot(inters - a, b - a), 0)) return true;
    return false;
}

bool segment_segment_intersect(point a, point b, point c, point d) {
    if (a.dist2(c) < EPS || a.dist2(d) < EPS ||
        b.dist2(c) < EPS || b.dist2(d) < EPS) return true;
    int d1, d2, d3, d4;
    d1 = direction(a, b, c);
    d2 = direction(a, b, d);
    d3 = direction(c, d, a);
    d4 = direction(c, d, b);
    if (d1 * d2 < 0 and d3 * d4 < 0) return 1;
    return a.on_seg(c, d) or b.on_seg(c, d) or
        c.on_seg(a, b) or d.on_seg(a, b);
}

bool segment_line_intersect(point a, point b, point c, point d) {
    if (!line_line_intersect(a, b, c, d)) return false;
    point inters = lines_intersect(a, b, c, d);
    if (inters.on_seg(a, b)) return true;
    return false;
}

//ray in direction c -> d
bool segment_ray_intersect(point a, point b, point c, point d) {
    if (a.dist2(c) < EPS || a.dist2(d) < EPS ||
        b.dist2(c) < EPS || b.dist2(d) < EPS) return true;
    if (lines_collinear(a, b, c, d)) {
        if (c.on_seg(a, b)) return true;
        if (ge(dot(d - c, a - c), 0)) return true;
        return false;
    }
    if (!line_line_intersect(a, b, c, d)) return false;
    point inters = lines_intersect(a, b, c, d);
    if (!inters.on_seg(a, b)) return false;
    if (ge(dot(inters - c, d - c), 0)) return true;
    return false;
}

//ray in direction a -> b
bool ray_line_intersect(point a, point b, point c, point d) {
    if (a.dist2(c) < EPS || a.dist2(d) < EPS ||
        b.dist2(c) < EPS || b.dist2(d) < EPS) return true;
    if (!line_line_intersect(a, b, c, d)) return false;
    point inters = lines_intersect(a, b, c, d);
    if (!line_line_intersect(a, b, c, d)) return false;
    if (ge(dot(inters - a, b - a), 0)) return true;
    return false;
}

ld distance_segment_line(point a, point b, point c, point d) {
    if (segment_line_intersect(a, b, c, d)) return 0;
    return min(distance_point_line(a, c, d), distance_point_line(b, c, d));
}

ld distance_segment_ray(point a, point b, point c, point d) {
    if (segment_ray_intersect(a, b, c, d)) return 0;
    ld min1 = distance_point_segment(c, a, b);
    ld min2 = min(distance_point_ray(a, c, d), distance_point_ray(b, c, d));
    return min(min1, min2);
}

ld distance_segment_segment(point a, point b, point c, point d) {
    if (segment_segment_intersect(a, b, c, d)) return 0;
    ld min1 = min(distance_point_segment(c, a, b), distance_point_segment(d, a, b));
    ld min2 = min(distance_point_segment(a, c, d), distance_point_segment(b, c, d));
    return min(min1, min2);
}

ld distance_ray_line(point a, point b, point c, point d) {
    if (ray_line_intersect(a, b, c, d)) return 0;
    ld min1 = distance_point_line(a, c, d);
    return min1;
}

ld distance_ray_ray(point a, point b, point c, point d) {
    if (ray_ray_intersect(a, b, c, d)) return 0;
    ld min1 = min(distance_point_ray(c, a, b), distance_point_ray(a, c, d));
    return min1;
}

ld distance_line_line(point a, point b, point c, point d) {
    if (line_line_intersect(a, b, c, d)) return 0;
    return distance_point_line(a, c, d);
}

struct circle {
    point c;
    ld r;
    circle() { c = point(); r = 0; }
    circle(point _c, ld _r) : c(_c), r(_r) {}
    ld area() { return acos(-1.0) * r * r; }
    ld chord(ld rad) { return  2 * r * sin(rad / 2.0); }
    ld sector(ld rad) { return 0.5 * rad * area() / acos(-1.0); }
    bool intersects(circle other) {
        return le(c.dist(other.c), r + other.r);
    }
    bool contains(point p) { return le(c.dist(p), r); }
    pair<point, point> getTangentPoint(point p) {
        ld d1 = c.dist(p), theta = asin(r / d1);
        point p1 = (c - p).rotate(-theta);
        point p2 = (c - p).rotate(theta);
        p1 = p1 * (sqrt(d1 * d1 - r * r) / d1) + p;
        p2 = p2 * (sqrt(d1 * d1 - r * r) / d1) + p;
        return make_pair(p1, p2);
    }
};

circle circumcircle(point a, point b, point c) {
    circle ans;
    point u = point((b - a).y, -(b - a).x);
    point v = point((c - a).y, -(c - a).x);
    point n = (c - b) * 0.5;
    ld t = cross(u, n) / cross(v, u);
    ans.c = ((a + c) * 0.5) + (v * t);
    ans.r = ans.c.dist(a);
    return ans;
}

point compute_circle_center(point a, point b, point c) {
    //circumcenter
    b = (a + b) / 2;
    c = (a + c) / 2;
    return compute_line_intersection(b, b + rotate_cw90(a - b), c, c + rotate_cw90(a - c));
}

int inside_circle(point p, circle c) {
    if (fabs(p.dist(c.c) - c.r) < EPS) return 1;
    else if (p.dist(c.c) < c.r) return 0;
    else return 2;
} //0 = inside/1 = border/2 = outside

circle incircle(point p1, point p2, point p3) {
    ld m1 = p2.dist(p3);
    ld m2 = p1.dist(p3);
    ld m3 = p1.dist(p2);
    point c = (p1 * m1 + p2 * m2 + p3 * m3) * (1 / (m1 + m2 + m3));
    ld s = 0.5 * (m1 + m2 + m3);
    ld r = sqrt(s * (s - m1) * (s - m2) * (s - m3)) / s;
    return circle(c, r);
}

circle minimum_circle(vector<point> p) {
    random_shuffle(p.begin(), p.end());
    circle C = circle(p[0], 0.0);
    for (int i = 0; i < (int)p.size(); i++) {
        if (C.contains(p[i])) continue;
        C = circle(p[i], 0.0);
        for (int j = 0; j < i; j++) {
            if (C.contains(p[j])) continue;
            C = circle((p[j] + p[i]) * 0.5, 0.5 * p[j].dist(p[i]));
            for (int k = 0; k < j; k++) {
                if (C.contains(p[k])) continue;
                C = circumcircle(p[j], p[i], p[k]);
            }
        }
    }
    return C;
}

// compute intersection of line through points a and b with
// circle centered at c with radius r > 0
vector<point> circle_line_intersection(point a, point b, point c, ld r) {
    vector<point> ret;
    b = b - a;
    a = a - c;
    ld A = dot(b, b);
    ld B = dot(a, b);
    ld C = dot(a, a) - r * r;
    ld D = B * B - A * C;
    if (D < -EPS) return ret;
    ret.push_back(c + a + b * (sqrt(D + EPS) - B) / A);
    if (D > EPS)
        ret.push_back(c + a + b * (-B - sqrt(D)) / A);
    return ret;
}

vector<point> circle_circle_intersection(point a, point b, ld r, ld R) {
    vector<point> ret;
    ld d = sqrt(a.dist2(b));
    if (d > r + R || d + min(r, R) < max(r, R)) return ret;
    ld x = (d * d - R * R + r * r) / (2 * d);
    ld y = sqrt(r * r - x * x);
    point v = (b - a) / d;
    ret.push_back(a + v * x + rotate_ccw90(v) * y);
    if (y > 0)
        ret.push_back(a + v * x - rotate_ccw90(v) * y);
    return ret;
}

//GREAT CIRCLE

double gcTheta(double pLat, double pLong, double qLat, double qLong) {
    pLat *= acos(-1.0) / 180.0; pLong *= acos(-1.0) / 180.0; // convert degree to radian
    qLat *= acos(-1.0) / 180.0; qLong *= acos(-1.0) / 180.0;
    return acos(cos(pLat) * cos(pLong) * cos(qLat) * cos(qLong) +
        cos(pLat) * sin(pLong) * cos(qLat) * sin(qLong) +
        sin(pLat) * sin(qLat));
}

double gcDistance(double pLat, double pLong, double qLat, double qLong, double radius) {
    return radius * gcTheta(pLat, pLong, qLat, qLong);
}

// getting the angle at point b
long double angle(point a, point b, point c) {
    long double ab = a.dist(b), ac = a.dist(c), bc = b.dist(c);
    long double tmp = ab * ab + bc * bc - ac * ac;
    tmp /= 2 * ab * bc;
    return fabs(acosl(tmp));
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << setprecision(15) << fixed;
    int n;
    cin >> n;
    vector<point> v(n);
    for(int i = 0; i < n; i++) {
        cin >> v[i].x >> v[i].y;
    }
    long double ans = 0;
    for(int i = 0; i < n; i++) {
        // cout << i << "\n";
        point pr = v[(i - 1 + n) % n], prr = v[(i - 2 + n) % n], pl = v[(i + 1) % n], pll = v[(i + 2) % n];
        point mid = (pl + pr) / 2;
        long double base = pl.dist(v[i]) + pr.dist(v[i]);
        long double rad = pl.dist(pr) / 2;
        point p = mid + rotate_ccw90((pr - pl) / 2);
        if(direction(pll, pl, p) == -1 and direction(prr, pr, p) == 1 and ge(angle(pll, pl, p), PI / 2) and ge(angle(prr, pr, p), PI / 2)) {
            // cout << "on circle\n";
            // cout << rad * 2 * sqrtl(2) - base << "\n";
            ans = max(ans, rad * 2 * sqrtl(2) - base);
        }
        if(line_line_intersect(pll, pl, prr, pr)) {
            point inter = lines_intersect(pll, pl, prr, pr);
            if(direction(pl, pr, inter) == 1 and ge(angle(pl, inter, pr), PI / 2)) {
                // cout << "line line intersect\n";
                // cout << pl.dist(inter) + pr.dist(inter) - base << "\n";
                // cout << inter << "\n";
                // cout << direction(pl, pr, inter) << "\n";
                ans = max(ans, pl.dist(inter) + pr.dist(inter) - base);
            }
        }
        //maybe middle do not work so grab the arc
        //each point will have a left boundary and right boundary which by default is arc(pl, pr), but maybe the possible arc is smaller than the whole arc
        point pr_lb = pl, pr_rb = pr, pl_lb = pl, pl_rb = pr;
        auto inter = circle_line_intersection(pl, pll, mid, rad);
        for(auto a : inter) {
            if(direction(prr, pr, a) == 1 and direction(pl, pr, a) != -1) {
                // cout << "circle line left\n";
                // cout << pl.dist(a) + pr.dist(a) - base << "\n";
                // cout << a << "\n";
                ans = max(ans, pl.dist(a) + pr.dist(a) - base);
                pl_lb = a;
            }
        }
        inter = circle_line_intersection(pr, prr, mid, rad);
        for(auto a : inter) {
            if (direction(pll, pl, a) == -1 and direction(pl, pr, a) != -1) {
                // cout << "circle line right\n";
                // cout << pl.dist(a) + pr.dist(a) - base << "\n";
                // cout << a << "\n";
                ans = max(ans, pl.dist(a) + pr.dist(a) - base);
                pr_rb = a;
            }
        }
        inter = circle_line_intersection(pr, pr + rotate_ccw90(pr - prr), mid, rad);
        for(auto a : inter) {
            if(eq(a.dist(pr), 0)) continue;
            if(direction(pl, pr, a) != -1) pr_lb = a;
        }
        inter = circle_line_intersection(pl, pl + rotate_cw90(pl - pll), mid, rad);
        for(auto a : inter) {
            if(eq(a.dist(pl), 0)) continue;
            if(direction(pl, pr, a) != -1) pl_rb = a;
        }
        //use boundaries to update answer, it will either improve or stay the same, e.g. boundary is pl or pr.
        //for each boundary point it must be inside the boundary defined by the other point, e.g. pl_al must be inside the arc(pr_al, pr_ar).
        //pr_lb
        if (direction(mid, pl_lb, pr_lb) != 1 and direction(mid, pl_rb, pr_lb) != -1) ans = max(ans, pl.dist(pr_lb) + pr.dist(pr_lb) - base);
        //pr_rb
        if (direction(mid, pl_lb, pr_rb) != 1 and direction(mid, pl_rb, pr_rb) != -1) ans = max(ans, pl.dist(pr_rb) + pr.dist(pr_rb) - base);
        //pl_lb
        if (direction(mid, pr_lb, pl_lb) != 1 and direction(mid, pr_rb, pl_lb) != -1) ans = max(ans, pl.dist(pl_lb) + pr.dist(pl_lb) - base);
        //pl_rb
        if (direction(mid, pr_lb, pl_rb) != 1 and direction(mid, pr_rb, pl_rb) != -1) ans = max(ans, pl.dist(pl_rb) + pr.dist(pl_rb) - base);
    }
    cout << ans << "\n";
    return 0;
}