intersection of half-planes

题目链接:多边形是否存在核

s&i:

struct point
{
    double x,y;
    point(double x=0,double y=0):
        x(x),y(y) {}
} p[55];
struct line
{
    point st,ed;
    double angle;
    line(double x1=0,double y1=0,double x2=0,double y2=0):
        st(x1,y1),ed(x2,y2) {}
    void get_angle()
    {
        angle=atan2(ed.y-st.y,ed.x-st.x);
    }
} l[55];

bool to_left(const point& p,const line& l)
{
    double x1=l.ed.x-l.st.x,y1=l.ed.y-l.st.y;
    double x2=p.x-l.st.x,y2=p.y-l.st.y;
    return x1*y2-x2*y1>-eps;
}

point get_jd(const line& l1,const line& l2)
{
    double x1=l1.st.x,y1=l1.st.y,x2=l1.ed.x,y2=l1.ed.y;
    double x3=l2.st.x,y3=l2.st.y,x4=l2.ed.x,y4=l2.ed.y;
    double k1=(x4-x3)*(y2-y1),k2=(x2-x1)*(y4-y3);
    double ans_x=(k1*x1-k2*x3+(y3-y1)*(x2-x1)*(x4-x3))/(k1-k2);
    double ans_y=(k2*y1-k1*y3+(x3-x1)*(y2-y1)*(y4-y3))/(k2-k1);
    return point(ans_x,ans_y);
}

bool cmp(const line& l1,const line& l2)
{
    if(fabs(l1.angle-l2.angle)>eps)
        return l1.angle>l2.angle;
    return to_left(l1.st,l2);
}

line deq[105];

int bpmj(int n)
{
    sort(l+1,l+n+1,cmp);
    int cont=0;
    for(int i=1; i<=n; i++)
        if(fabs(l[i].angle-l[cont].angle)>eps)
            l[++cont]=l[i];
    int le=1,ri=1;
    for(int i=1; i<=cont; i++)
    {
        while(ri>le+1 && !to_left(get_jd(deq[ri-1],deq[ri-2]),l[i]))ri--;
        while(ri>le+1 && !to_left(get_jd(deq[le],deq[le+1]),l[i]))le++;
        deq[ri++]=l[i];
    }
    while(ri>le+2 && !to_left(get_jd(deq[ri-1],deq[ri-2]),deq[le]))ri--;
    while(ri>le+2 && !to_left(get_jd(deq[le],deq[le+1]),deq[ri-1]))le++;
    if(ri>le+2)return 1;
    return 0;
}

int main()
{
    int n;
    while(~scanf("%d",&n) && n)
    {
        for(int i=1; i<=n; i++)
            scanf("%lf%lf",&p[i].x,&p[i].y);
        p[n+1]=p[1];
        for(int i=1; i<=n; i++)
        {
            l[i]=line(p[i].x,p[i].y,p[i+1].x,p[i+1].y);
            l[i].get_angle();
        }
        printf("%d\n",bpmj(n));
    }
    return 0;
}

题目链接:多边形核的面积

s&i:

struct point
{
    double x,y;
    point(double x=0,double y=0):
        x(x),y(y) {}
} p[1505];
struct line
{
    point st,ed;
    double angle;
    line(double x1=0,double y1=0,double x2=0,double y2=0):
        st(x1,y1),ed(x2,y2) {}
    void get_angle()
    {
        angle=atan2(ed.y-st.y,ed.x-st.x);
    }
} l[1505];

double cross(const point& st,const point& fir,const point& sec)
{
    double x1=fir.x-st.x,y1=fir.y-st.y;
    double x2=sec.x-st.x,y2=sec.y-st.y;
    return x1*y2-x2*y1;
}

bool to_left(const point& p,const line& l)
{
    double x1=l.ed.x-l.st.x,y1=l.ed.y-l.st.y;
    double x2=p.x-l.st.x,y2=p.y-l.st.y;
    return x1*y2-x2*y1>-eps;
}

point get_jd(const line& l1,const line& l2)
{
    double x1=l1.st.x,y1=l1.st.y,x2=l1.ed.x,y2=l1.ed.y;
    double x3=l2.st.x,y3=l2.st.y,x4=l2.ed.x,y4=l2.ed.y;
    double k1=(x4-x3)*(y2-y1),k2=(x2-x1)*(y4-y3);
    double ans_x=(k1*x1-k2*x3+(y3-y1)*(x2-x1)*(x4-x3))/(k1-k2);
    double ans_y=(k2*y1-k1*y3+(x3-x1)*(y2-y1)*(y4-y3))/(k2-k1);
    return point(ans_x,ans_y);
}

bool cmp(const line& l1,const line& l2)
{
    if(fabs(l1.angle-l2.angle)>eps)
        return l1.angle>l2.angle;
    return to_left(l1.st,l2);
}

line deq[1505];

double bpmj(int n)
{
    sort(l+1,l+n+1,cmp);
    int cont=0;
    for(int i=1; i<=n; i++)
        if(fabs(l[i].angle-l[cont].angle)>eps)
            l[++cont]=l[i];
    int le=1,ri=1;
    for(int i=1; i<=cont; i++)
    {
        while(ri>le+1 && !to_left(get_jd(deq[ri-1],deq[ri-2]),l[i]))ri--;
        while(ri>le+1 && !to_left(get_jd(deq[le],deq[le+1]),l[i]))le++;
        deq[ri++]=l[i];
    }
    while(ri>le+2 && !to_left(get_jd(deq[ri-1],deq[ri-2]),deq[le]))ri--;
    while(ri>le+2 && !to_left(get_jd(deq[le],deq[le+1]),deq[ri-1]))le++;
    if(ri<=le+2)return 0.0;
    deq[ri]=deq[le],cont=0;
    for(int i=le; i<ri; i++)
        p[++cont]=get_jd(deq[i],deq[i+1]);
    double ans=0.0;
    for(int i=2; i<cont; i++)
        ans+=fabs(cross(p[1],p[i],p[i+1]))/2;
    return ans;
}

int main()
{
    int T,n;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i=1; i<=n; i++)
            scanf("%lf%lf",&p[i].x,&p[i].y);
        p[n+1]=p[1];
        for(int i=1; i<=n; i++)
        {
            l[i]=line(p[i+1].x,p[i+1].y,p[i].x,p[i].y);
            l[i].get_angle();
        }
        printf("%.2lf\n",bpmj(n));
    }
    return 0;
}