国内予選2015 G. 複雑な折り紙

くるくるドア(模擬国内予選G)の担当者であるnotさんとMi_Sawaさんが揃ってGを解いておられたので，
ライブラリをぺたぺたして解いてみた次第．
方針は，外周の候補を列挙後に折り線基準で偏角ソートして，
どっちかの多角形に内包(strictly)されているものを除くという感じ．
とりあえずサンプルは通った．

// ACM-ICPC国内予選2015 G. 複雑な折り紙

#include <iostream>
#include <vector>
#include <complex>
#include <algorithm>
#include <cstdio>

using namespace std;

typedef complex<double> P;
typedef vector<P> G;

const double EPS = 1e-8;

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

double dot(const P& a, const P& b) { return real(conj(a)*b); }
double cross(const P& a, const P& b) { return imag(conj(a)*b); }
double angle(const P& a, const P& b) { return arg(conj(a)*b); }

bool ssIntersect(const L& a, const L& b){
    if(abs(imag((a.q-a.p)/(b.q-b.p))) < EPS) return false;
    return cross(a.q-a.p, b.p-a.p)*cross(a.q-a.p, b.q-a.p) < 0 &&
           cross(b.q-b.p, a.p-b.p)*cross(b.q-b.p, a.q-b.p) < 0;
}

P ssCrosspoint(const L& a, const L& b){
    double A = cross(a.q-a.p, b.q-b.p);
    double B = cross(a.q-a.p, a.q-b.p);
    return b.p + B/A * (b.q-b.p);
}

G convexCut(const G& g, const P& p, const P& q){
    G res;
    int n = g.size();
    for(int i=0;i<n;i++){
        P A(g[i]), B(g[(i+1)%n]);
        double p1 = cross(q-p, A-p);
        double p2 = cross(q-p, B-p);
        if(p1 > -EPS) res.push_back(A);
        if(p1*p2 < -EPS)
            res.push_back(A+cross(q-p, q-A)/cross(q-p, B-A)*(B-A));
    }
    return res;
}

bool contains(const G& g, const P& p){
    bool in = false;
    for(int i=0;i<g.size();i++){
        P a(g[i]-p), b(g[(i+1)%g.size()]-p);
        if(imag(a) > imag(b)) swap(a,b);
        if(imag(a)<=0&&0<imag(b))
            if(cross(a,b)<0) in = !in;
        if(abs(cross(a,b))<EPS&&dot(a,b)<EPS) return false;
    }
    return in;
}

P footPerp(const L& l, const P& p) {
    return l.p + (l.q-l.p)*(dot(l.q-l.p, p-l.p) / norm(l.q-l.p));
}

P lineShadow(const L& l, const P& p){
    return 2.0*footPerp(l, p)-p;
}

pair<int, double> solve(const G& poly, const L& cut){
    G g1 = convexCut(poly, cut.p, cut.q);
    G g2 = convexCut(poly, cut.q, cut.p);
    P p0(0, 0);
    int addNum = 0;
    for(const P& p : g1){
        if(abs(cross(p-cut.p, cut.q-cut.p)) < EPS){
            p0 = p0 + p;
            addNum++;
        }
    }
    for(P& p : g2){
        p = lineShadow(cut, p);
    }
    p0 = p0/(double)addNum;
    vector<pair<double, P>> vp;
    for(const P& p : g1){
        double agl = angle(cut.q-cut.p, p-p0);
        vp.push_back(make_pair(agl, p));
    }
    for(const P& p : g2){
        double agl = angle(cut.q-cut.p, p-p0);
        vp.push_back(make_pair(agl, p));
    }
    for(int i=0;i<g1.size();i++){
        L l1(g1[i], g1[(i+1)%g1.size()]);
        for(int j=0;j<g2.size();j++){
            L l2(g2[j], g2[(j+1)%g2.size()]);
            if(ssIntersect(l1, l2)){
                P cp = ssCrosspoint(l1, l2);
                double agl = angle(cut.q-cut.p, cp-p0);
                vp.push_back(make_pair(agl, cp));
            }
        }
    }
    sort(vp.begin(),
        vp.end(),
        [](const pair<double, P>& a, const pair<double, P>& b){
            return a.first < b.first;
        }
    );
    G out;
    for(const pair<double, P>& pr : vp){
        const P& p = pr.second;
        if(!contains(g1, p) && !contains(g2, p)){
            int n = out.size();
            if(n >= 1){
                if(norm(out.back() - p) < EPS) continue;
            }
            if(n >= 2){
                if(abs(cross(out[n-1]-out[n-2], p-out[n-2])) < EPS){
                    out.back() = p;
                    continue;
                }
            }
            out.push_back(p);
        }
    }
    if(norm(out[0] - out.back()) < EPS) out.pop_back();
    pair<int, double> res(out.size(), 0);
    for(int i=0;i<out.size();i++){
        res.second += abs(out[i] - out[(i+1)%out.size()]);
    }
    return res;
}

int main(){
    int n;
    while(cin >> n && n){
        G g(n);
        for(int i=0;i<n;i++){
            int x, y; cin >> x >> y;
            g[i] = P(x,y);
        }
        pair<int, double> res(0, 0);
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                P mid = 0.5*(g[i]+g[j]);
                P dir = (g[j]-g[i])*P(0, 1) + mid;
                L l(mid, dir);
                res = max(res, solve(g, l));
            }
        }
        printf("%.8lf\n", res.second);
    }
}