C++ 解法, 执行用时: 3ms, 内存消耗: 424K, 提交时间: 2021-10-26 16:58:25

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define db double
const int N=100;
const db eps=1e-9,inf=1e18;
ll t,n,m;

int sign(db k) { return k<-eps? -1: (k>eps? 1: 0); }
struct poi
{
    db x,y;
    poi operator+(const poi& a) const { return poi{x+a.x,y+a.y}; }
    poi operator-(const poi& a) const { return poi{x-a.x,y-a.y}; }
    poi operator*(const db& k) const { return poi{x*k,y*k}; }
};
db Cro(poi a,poi b) { return a.x*b.y-a.y*b.x; }
db Dot(poi a,poi b) { return a.x*b.x+a.y*b.y; }
db Len(poi a) { return sqrt(Dot(a,a)); }

poi ps[N],s;

//返回切点占AB比例，距A比例
db divR(poi a,poi b,poi c,poi d)
{
    poi t1=a-b,t2=c-d,t3=a-c;
    if(sign(Cro(t1,t2))==0) return -inf;
    db ret = (Cro(t3,t2)) / (Cro(t1,t2));
    return sign(ret)>=0 && sign(ret-1)<=0 ? ret:-inf;
}

//判线段相交
bool pan_cross_LL(poi a,poi b,poi c,poi d)
{
    db c1=Cro(b-a,c-a),c2=Cro(b-a,d-a);
    db d1=Cro(d-c,a-c),d2=Cro(d-c,b-c);
    return sign(c1)*sign(c2)<=0 && sign(d1)*sign(d2)<=0;
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i=1;i<=n;i++) cin>>ps[i].x>>ps[i].y;
        ps[n+1]=ps[1];
        cin>>s.x>>s.y;
        db ans=0;
        for(int i=1;i<=n;i++)
        {
            vector<db> cp;
            for(int j=1;j<=n;j++)
            {
                db ins=divR(ps[i],ps[i+1],s,ps[j]);
                if(ins>=-1) cp.push_back(ins);
            }
            sort(cp.begin(),cp.end());
            db rate=0;
            for(int j=0;j<(int)cp.size()-1;j++)
            {
                poi cut=ps[i]+(ps[i+1]-ps[i])*((cp[j]+cp[j+1])/2);
                bool isok=0;
                for(int k=1;k<=n;k++)
                {
                    if(k==i) continue;
                    if(pan_cross_LL(s,cut,ps[k],ps[k+1]))
                    {
                        isok=1;break;
                    }
                }
                if(!isok) rate+=cp[j+1]-cp[j];
            }
            ans+=rate*Len(ps[i+1]-ps[i]);
        }
        cout<<fixed<<setprecision(12)<<ans<<"\n";
    }

    return 0;
}