れんしゅうちょう。

notさんのを見習って僕も書いてみた.

方針は zerokugiさんのと同じ.

線分をむりやり符号付きにしてやると楽なようだ.

サンプルは通った.

ライブラリ除いて50行くらい.

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (n); ++i)

#define X real()
#define Y imag()
using R = long double;
using P = complex<R>;
using L = pair<P, P>;
const R EPS = 1E-8;
#define fst first
#define snd second
inline int sgn(const R &r){ return (r > EPS) - (r < -EPS); }
inline int sgn(const R &a, const R &b){ return sgn(a-b); }
namespace std{
    bool operator<(const P &a, const P &b){
        return sgn(a.X, b.X) ? a.X < b.X : sgn(a.Y, b.Y) < 0;
    }
}
inline R dot(const P &a, const P &b){ return real(conj(a) * b); }
inline R det(const P &a, const P &b){ return imag(conj(a) * b); }
inline P vec(const L &l){ return l.snd - l.fst; }
enum CCW{FRONT = 1, RIGHT = 2, BACK = 4, LEFT = 8, ON = 16, };
inline int ccw(const L &l, const P &p){
    P b = p - l.fst, c = l.snd - l.fst;
    if(int scr = sgn(det(c, b))) return scr < 0 ? RIGHT : LEFT;
    if(sgn(dot(c, b)) < 0) return BACK;
    return sgn(norm(c), norm(b)) < 0 ? FRONT : ON;
}
inline vector<P> pLL(const L &l, const L &m){
    if(sgn(det(vec(l), vec(m))) == 0) return vector<P>(0);
    R A = det(vec(m), vec(l));
    R B = det(vec(m), m.snd - l.fst);
    return vector<P>(1, l.fst + B / A * vec(l));
}
inline P refLP(const L &l, const P &p){
    return (R)(2) * (l.fst + dot(p - l.fst, vec(l)) / norm(vec(l)) * vec(l)) - p;
}
vector<P> cut(const vector<P> &pol, const L &l){
    vector<P> res;
    rep(i, pol.size()-1){
        P a = pol[i], b = pol[i+1];
        L s(a, b);
        if(ccw(l, a) != RIGHT) res.emplace_back(a);
        if(sgn(det(vec(l), s.fst-l.fst)) * sgn(det(vec(l), s.snd-l.fst)) < 0)
            res.emplace_back(pLL(l, s).front());
    }
    res.emplace_back(res.front());
    return res;
}

bool solve(){
    int n; cin >> n;
    if(!n) return false;
    vector<P> in(n);
    for(auto &p : in){ R x, y; cin >> x >> y; p.real(x); p.imag(y); }
    in.emplace_back(in.front());
    pair<int, R> res(-1, 0);
    rep(i, n) rep(j, i){
        L l((in[i] + in[j]) / (R)(2), P(0, 0));
        l.snd = l.fst + P(0, 1) * (in[i] - in[j]);

        vector<P> a = cut(in, l); swap(l.fst, l.snd);
        vector<P> b = cut(in, l);
        for(auto &p : b) p = refLP(l, p);
        reverse(begin(b), end(b));

        vector<P> c = b;
        rep(i, a.size()-1) c = cut(c, L(a[i], a[i+1]));

        vector<P> ps;
        for(auto &p : a) ps.emplace_back(p);
        for(auto &p : b) ps.emplace_back(p);
        for(auto &p : c) ps.emplace_back(p);
        auto near = [](const P &a, const P &b){ return sgn(abs(a-b)) == 0; };
        sort(begin(ps), end(ps));
        ps.erase(unique(begin(ps), end(ps), near), end(ps));

        vector<pair<L, int>> ls;
        rep(i, a.size()-1) ls.emplace_back(L(a[i], a[i+1]), +1);
        rep(i, b.size()-1) ls.emplace_back(L(b[i], b[i+1]), +1);
        rep(i, c.size()-1) ls.emplace_back(L(c[i], c[i+1]), -1);

        R len = 0;
        for(auto &ld : ls) len += ld.snd * abs(ld.fst.snd - ld.fst.fst);

        map<pair<int, int>, int> es;
        for(auto &ld : ls){
            vector<pair<P, int>> qs;
            rep(i, ps.size()) if(ccw(ld.fst, ps[i]) == ON) qs.emplace_back(ps[i], i);
            sort(begin(qs), end(qs));
            rep(i, qs.size()-1) es[make_pair(qs[i].snd, qs[i+1].snd)] += ld.snd;
            rep(i, qs.size()-1) es[make_pair(qs[i+1].snd, qs[i].snd)] += ld.snd;
        }
        int cnt = 0;
        vector<vector<P>> g(ps.size());
        for(auto &e : es) if(e.snd) g[e.fst.fst].emplace_back(ps[e.fst.snd]);
        for(auto &v : g) assert(v.size() == 0 or v.size() == 2);
        rep(i, g.size()) if(g[i].size() == 2) cnt += ccw(L(g[i][0], g[i][1]), ps[i]) != ON;
        res = max(res, make_pair(cnt, len));
    }
    printf("%.6Lf\n", res.snd);
    return true;
}

int main(void){
    while(solve());
}

ツイートする