Paimon Polygon

C++(clang++ 11.0.1) 解法, 执行用时: 811ms, 内存消耗: 47776K, 提交时间: 2022-09-02 20:36:51
#include <bits/stdc++.h>
using namespace std;

//const double eps=1e-8;
const long long eps=0;
const double PI=3.1415926535897932384l;

template<typename T> struct point
{
    T x,y;

    bool operator==(const point &a) const {return (abs(x-a.x)<=eps && abs(y-a.y)<=eps);}
    bool operator<(const point &a) const {if (abs(x-a.x)<=eps) return y<a.y-eps; return x<a.x-eps;}
    point operator+(const point &a) const {return {x+a.x,y+a.y};}
    point operator-(const point &a) const {return {x-a.x,y-a.y};}
    point operator-() const {return {-x,-y};}
    point operator*(const T k) const {return {k*x,k*y};}
    point operator/(const T k) const {return {x/k,y/k};}
    T operator*(const point &a) const {return x*a.x+y*a.y;} //Dot
    T operator^(const point &a) const {return x*a.y-y*a.x;} //Cross
    int toleft(const point &a) const {auto t=(*this)^a; return (t>eps)-(t<-eps);}
    T len2() const {return (*this)*(*this);}
    T dis2(const point &a) const {return (a-(*this)).len2();}
    double len() const {return sqrt(len2());}
    double dis(const point &a) const {return sqrt(dis2(a));}
    double ang(const point &a) const {return acos(max(-1.0,min(1.0,((*this)*a)/(len()*a.len()))));}
    point rot(const double rad) const {return {x*cos(rad)-y*sin(rad),x*sin(rad)+y*cos(rad)};}
};

using Point=point<long long>;

bool argcmp(const Point &a,const Point &b)
{
    auto quad=[](const Point &a)
    {
        if (a.y<-eps) return 1;
        if (a.y>eps) return 4;
        if (a.x<-eps) return 5;
        if (a.x>eps) return 3;
        return 2;
    };
    int qa=quad(a),qb=quad(b);
    if (qa!=qb) return qa<qb;
    auto t=a^b;
    if (abs(t)<=eps) return a*a<b*b-eps;
    return t>eps;
}

template<typename T> struct line
{
    point<T> p,v;

    bool operator==(const line &a) const {return (v.is_par(a.v) && v.is_par(p-a.p));}
    int toleft(const point<T> &a) const {return v.toleft(a-p);}
    point<T> inter(const line &a) const {return p+v*((a.v^(p-a.p))/(v^a.v));}
    double dis(const point<T> &a) const {return abs(v^(a-p))/v.len();}
    point<T> proj(const point<T> &a) const {return p+v*((v*(a-p))/(v*v));}
    /*bool operator<(const line &a) const
    {
        if (abs(v^a.v)<=eps && v*a.v>=-eps) return toleft(a.p)==-1;
        return argcmp(v,a.v);
    }*/
};

using Line=line<long long>;

bool ponseg(const Point &u,const Point &v,const Point &p)
{
    return ((u-p)^(v-p))==0 && (u-p)*(v-p)<=0;
}

template<typename T> struct polygon
{
    vector<Point> p;

    inline size_t nxt(const size_t i) const {return i==p.size()-1?0:i+1;}
    inline size_t pre(const size_t i) const {return i==0?p.size()-1:i-1;}

    pair<bool,int> winding(const Point &a) const
    {
        int cnt=0;
        for (size_t i=0;i<p.size();i++)
        {
            Point u=p[i],v=p[nxt(i)];
            if (abs((a-u)^(a-v))<=eps && (a-u)*(a-v)<=eps) return {true,0};
            if (abs(u.y-v.y)<=eps) continue;
            Line uv={u,v-u};
            if (u.y<v.y-eps && uv.toleft(a)<=0) continue;
            if (u.y>v.y+eps && uv.toleft(a)>=0) continue;
            if (u.y<a.y-eps && v.y>=a.y-eps) cnt++;
            if (u.y>=a.y-eps && v.y<a.y-eps) cnt--;
        }
        return {false,cnt};
    }

    bool is_in(const Point &a) const //convex
    {
        size_t l=1,r=p.size()-2;
        while (l<=r)
        {
            auto mid=(l+r)>>1;
            auto a1=(p[mid]-p[0])^(a-p[0]),a2=(p[mid+1]-p[0])^(a-p[0]);
            if (a1>=-eps && a2<=eps)
            {
                if (mid==1 && ponseg(p[0],p[mid],a)) return false;
                if (mid+1==p.size()-1 && ponseg(p[0],p[mid+1],a)) return false;
                if (ponseg(p[mid],p[mid+1],a)) return false;
                if (((p[mid+1]-p[mid])^(a-p[mid]))>=-eps) return true;
                return false;
            }
            if (a1<-eps) r=mid-1;
            else l=mid+1;
        }
        return false;
    }

    double circ() const
    {
        double sum=0;
        for (size_t i=0;i<p.size();i++) sum+=p[i].dis(p[nxt(i)]);
        return sum;
    }

    T area2() const
    {
        T sum=0;
        for (size_t i=0;i<p.size();i++) sum+=p[i]^p[nxt(i)];
        return abs(sum);
    }
};

using Polygon=polygon<long long>;

#define back1(x) x.back()
#define back2(x) *(x.rbegin()+1)

//Andrew
Polygon convex(vector<Point> p)
{
    vector<Point> st;
    sort(p.begin(),p.end());
    for (Point u:p)
    {
        while (st.size()>1 && (back1(st)-back2(st)).toleft(u-back2(st))<=0) st.pop_back();
        st.push_back(u);
    }
    size_t k=st.size();
    p.pop_back(); reverse(p.begin(),p.end());
    for (Point u:p)
    {
        while (st.size()>k && (back1(st)-back2(st)).toleft(u-back2(st))<=0) st.pop_back();
        st.push_back(u);
    }
    st.pop_back();
    return {st};
}

int T,n,x,y;

double solve1(vector<Point> vec)
{
    vec.push_back({0,0});
    Polygon poly_out=convex(vec);
    if (poly_out.p.size()<=2) return 0;
    set<Point> s;
    for (Point u:poly_out.p) s.insert(u);
    if (!s.count({0,0})) return 0;
    vector<Point> inner;
    for (Point u:vec)
    {
        if (s.count(u)) continue;
        if (!poly_out.is_in(u)) return 0;
        inner.push_back(u);
    }
    inner.push_back({0,0});
    Polygon poly_in=convex(inner);
    if (poly_in.p.size()<=2) return 0;
    if ((int)poly_out.p.size()+(int)poly_in.p.size()<n+2) return 0;
    return poly_in.circ()+poly_out.circ();
}

bool is_in(size_t l,size_t r,size_t x,size_t siz)
{
    if (r<l) r+=siz;
    return (x>l && x<r) || (x+siz>l && x+siz<r);
}

bool cover(const Point &u,const Point &v)
{
    return u.toleft(v)==0 && u*v>=0;
}

bool check(const Polygon &poly,const unordered_set<size_t> &non,size_t i,size_t j)
{
    auto _i=poly.nxt(i),_j=poly.nxt(j);
    if (j==_i) return false;
    if (i==_j) return false;
    if (poly.p[_i].toleft(poly.p[j])<=0 || poly.p[_j].toleft(poly.p[i])<=0) return false;
    if (cover(poly.p[i],poly.p[_i])) return false;
    if (cover(poly.p[j],poly.p[_j])) return false;
    if (cover(poly.p[_i],poly.p[poly.nxt(_i)])) return false;
    if (cover(poly.p[_j],poly.p[poly.nxt(_j)])) return false;
    if (cover(poly.p[i],poly.p[poly.pre(i)])) return false;
    if (cover(poly.p[j],poly.p[poly.pre(j)])) return false;
    for (auto t:non)
    {
        if (is_in(_i,j,t,poly.p.size())) return false;
        if (is_in(_j,i,t,poly.p.size())) return false;
    }
    return true;
}

double cal(const Point &u,const Point &v)
{
    return u.len()+v.len()-u.dis(v);
}

double solve2(vector<Point> vec)
{
    sort(vec.begin(),vec.end(),argcmp);
    Polygon poly={vec};
    unordered_set<size_t> non;
    double tot=0;
    auto siz=poly.p.size();
    for (size_t i=0;i<siz;i++)
    {
        auto prei=poly.pre(i),nxti=poly.nxt(i);
        Point u=poly.p[prei],v=poly.p[i],w=poly.p[nxti];
        if ((v-u).toleft(w-v)<=0) non.insert(i);
        tot+=v.dis(w);
    }
    double ans=0;
    vec.insert(vec.end(),vec.begin(),vec.end());
    for (size_t i=0,l=1,r=0;i<siz;i++)
    {
        while (l<vec.size() && l<i+siz && (l==i+1 || vec[i+1].toleft(vec[l])==1)) l++;
        while (r<vec.size() && r<i+siz && vec[i].toleft(vec[r])>=0) r++;
        auto _l=max(i+2,r-1),_r=min(l-1,i+siz-2);
        for (size_t j=_l;j<=_r;j++)
        {
            if (!check(poly,non,i%siz,j%siz)) continue;
            double d=cal(vec[i],vec[i+1])+cal(vec[j],vec[j+1]);
            ans=max(ans,tot+d);
        }
    }
    return ans;
}

int main()
{
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d",&n);
        vector<Point> vec;
        for (int i=1;i<=n;i++)
        {
            scanf("%d%d",&x,&y);
            vec.push_back({x,y});
        }
        double ans=max(solve1(vec),solve2(vec));
        printf("%.10lf\n",ans);
    }
    getchar(); getchar();
    return 0;
}
详情
