Loj 2008 小凸想跑步

\(S(P,p_0,p_1)<S(P,p_i,p_{i+1})\) 这个约束条件对于 \(P_x,P_y\) 是线性的,即将面积用向量叉积表示,暴力拆开,可得到 \(aP_x+bP_y+c<0\) 的形式,表示了一个半平面,其他每条边都确定了一个半平面.
再将 \(P\) 在多边形内拆成 \(N-1\) 个半平面的限制,将这 \(2N-1\) 个半平面求交,得到的区域即为合法区域,除以总面积即得答案

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

inline int read()

{

    int out=0,fh=1;

    char jp=getchar();

    while ((jp>'9'||jp<'0')&&jp!='-')

        jp=getchar();

    if (jp=='-')

        fh=-1,jp=getchar();

    while (jp>='0'&&jp<='9')

        out=out*10+jp-'0',jp=getchar();

    return out*fh;

}

const double eps=1e-8;

inline int dcmp(double x)

{

    if(fabs(x)<=eps)

        return 0;

    return x>0;

}

const int MAXN=2e5+10;

struct v2

{

    double x,y;

    v2(double x=0,double y=0):x(x),y(y) {}

    friend double operator * (const v2 &a,const v2 &b)

    {

        return a.x*b.y-a.y*b.x;

    }

    v2 operator + (const v2 &rhs) const

    {

        return v2(x+rhs.x,y+rhs.y);

    }

    v2 operator - (const v2 &rhs) const

    {

        return v2(x-rhs.x,y-rhs.y);

    }

    v2 operator ^ (const double &lambda) const

    {

        return v2(x*lambda,y*lambda);

    }

    double modulus()

    {

        return sqrt(x*x+y*y);

    }

    double angle()

    {

        return atan2(y,x);

    }

    bool operator < (const v2 &rhs) const

    {

        return x==rhs.x?y<rhs.y:x<rhs.x;

    }

};

struct Line

{

    v2 p,v;

    double angle()

    {

        return v.angle();

    }

    friend bool operator < (Line a,Line b)

    {

        if(a.angle()!=b.angle())

            return a.angle()<b.angle();

        return a.v*b.v<0;

    }

};

bool Onleft(Line L,v2 p)

{

    return (L.v*(p-L.p))>0;

}

v2 Intersection(Line a,Line b)

{

    v2 u=a.p-b.p;

    double t=(b.v*u)/(a.v*b.v);

    return a.p+(a.v^t);

}

#define x(I) poly[I].x

#define y(I) poly[I].y

int n,totl=0;

v2 poly[MAXN];

Line L[MAXN],q[MAXN];

v2 p[MAXN];

int head,tail;

void Hpi()

{

    sort(L+1,L+1+totl);

    q[head=tail=1]=L[1];

    for(int i=2;i<=totl;++i)

    {

        while(head<tail && !Onleft(L[i],p[tail-1]))

            --tail;

        while(head<tail && !Onleft(L[i],p[head]))

            ++head;

        ++tail;

        q[tail]=L[i];

        if(head<tail && (q[tail].v*q[tail-1].v)==0)

        {

            --tail;

            if(Onleft(q[tail],L[i].p))

                q[tail]=L[i];

        }

        if(head<tail)

            p[tail-1]=Intersection(q[tail-1],q[tail]);

    }

    while(head<tail && !Onleft(q[head],p[tail-1]))

        --tail;

    p[tail]=Intersection(q[tail],q[head]);

    p[tail+1]=p[head];

    double area=0;

    v2 O=v2(0,0);

    for(int i=head;i<=tail;++i)

        area+=(O-p[i])*(O-p[i+1]);

	area=fabs(area);

    double ts=0;

    for(int i=1;i<=n;++i)

        ts+=(O-poly[i])*(O-poly[i+1]);

    ts=fabs(ts);

    printf("%.4lf\n",area/ts);

}

int main()

{

    n=read();

    for(int i=1; i<=n; ++i)

        scanf("%lf%lf",&poly[i].x,&poly[i].y);

    poly[n+1]=poly[1];

    for(int i=1; i<=n; ++i)

    {

        ++totl;

        L[totl].p=poly[i];

        L[totl].v=poly[i+1]-poly[i];

    }

    for(int i=2; i<=n; ++i)

    {

    	int j=i+1;

        double a=x(2)-x(1),b=y(2)-y(1);

        double c=x(j)-x(i),d=y(j)-y(i);

        double A=d-b,B=a-c,C=b*x(1)-a*y(1)+c*y(i)-d*x(i);

        if(A==0 && B==0)

        {

        	if(C<=0)

        		continue;

        	else

        		return puts("0.0000")&0;

		}

		++totl;

		if(A==0)

			L[totl].p=v2(0,-C/B);

		else

			L[totl].p=v2(-C/A,0);

		L[totl].v=v2(-B,A);

		if(i!=n && !Onleft(L[totl],poly[1]))

			L[totl].v=(L[totl].v^(-1));

		if(i==n && !Onleft(L[totl],poly[2]))

			L[totl].v=(L[totl].v^(-1));

    }

    Hpi();

    return 0;

}

巴特西

Loj 2008 小凸想跑步

Loj 2008 小凸想跑步

最新文章

热门文章