POJ 2451 求半面交

简介:

题意:求半面想交后的面积,题目数据较大,使用o(n*logn)算法。

这题WA两次忘了m<3的情况,不应该啊= = 。

#include<cmath>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int mm=20005;
typedef double DIY;
struct point
{
    DIY x,y;
    point() {}
    point(DIY _x,DIY _y):x(_x),y(_y) {}
} g[mm];
double Direction(point pi,point pj,point pk) //判断向量PiPj在向量PiPk的顺逆时针方向 +顺-逆0共线
{
    return (pj.x-pi.x)*(pk.y-pi.y)-(pk.x-pi.x)*(pj.y-pi.y);
}
point MakeVector(point &P,point &Q)
{
    return point(Q.x-P.x,Q.y-P.y);
}
DIY CrossProduct(point P,point Q)
{
    return P.x*Q.y-P.y*Q.x;
}
DIY MultiCross(point P,point Q,point R)
{
    return CrossProduct(MakeVector(Q,P),MakeVector(Q,R));
}
struct halfPlane
{
    point s,t;
    double angle;
    halfPlane() {}
    halfPlane(point _s,point _t):s(_s),t(_t) {}
    halfPlane(DIY sx,DIY sy,DIY tx,DIY ty):s(sx,sy),t(tx,ty) {}
    void GetAngle()
    {
        angle=atan2(t.y-s.y,t.x-s.x);
    }
} hp[mm],q[mm];
point IntersectPoint(halfPlane P,halfPlane Q)
{
    DIY a1=CrossProduct(MakeVector(P.s,Q.t),MakeVector(P.s,Q.s));
    DIY a2=CrossProduct(MakeVector(P.t,Q.s),MakeVector(P.t,Q.t));
    return point((P.s.x*a2+P.t.x*a1)/(a2+a1),(P.s.y*a2+P.t.y*a1)/(a2+a1));
}
bool cmp(halfPlane P,halfPlane Q)
{
    if(fabs(P.angle-Q.angle)<1e-8)
        return MultiCross(P.s,P.t,Q.s)>0;
    return P.angle<Q.angle;
}
bool IsParallel(halfPlane P,halfPlane Q)
{
    return fabs(CrossProduct(MakeVector(P.s,P.t),MakeVector(Q.s,Q.t)))<1e-8;
}
void HalfPlaneIntersect(int n,int &m)
{
    sort(hp,hp+n,cmp);
    int i,l=0,r=1;
    for(m=i=1; i<n; ++i)
        if(hp[i].angle-hp[i-1].angle>1e-8)hp[m++]=hp[i];
    n=m;
    m=0;
    q[0]=hp[0],q[1]=hp[1];
    for(i=2; i<n; ++i)
    {
        if(IsParallel(q[r],q[r-1])||IsParallel(q[l],q[l+1]))return;
        while(l<r&&MultiCross(hp[i].s,hp[i].t,IntersectPoint(q[r],q[r-1]))>0)--r;
        while(l<r&&MultiCross(hp[i].s,hp[i].t,IntersectPoint(q[l],q[l+1]))>0)++l;
        q[++r]=hp[i];
    }
    while(l<r&&MultiCross(q[l].s,q[l].t,IntersectPoint(q[r],q[r-1]))>0)--r;
    while(l<r&&MultiCross(q[r].s,q[r].t,IntersectPoint(q[l],q[l+1]))>0)++l;
    q[++r]=q[l];
    for(i=l; i<r; ++i)
        g[m++]=IntersectPoint(q[i],q[i+1]);
}
int main()
{
    int n,m;
    point a,b;
    point p[5];
    p[0].x=0,p[0].y=0;
    p[1].x=10000,p[1].y=0;
    p[2].x=10000,p[2].y=10000;
    p[3].x=0,p[3].y=10000;
    while(~scanf("%d",&n))
    {
        for(int i=0; i<n; i++)
        {
            scanf("%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y);
            hp[i]=halfPlane(a,b);
            hp[i].GetAngle();
        }
        for(int i=0; i<4; i++)
        {
            hp[n+i]=halfPlane(p[i],p[(i+1)%4]);
            hp[i+n].GetAngle();
        }
        HalfPlaneIntersect(n+4,m);
        if(m<3)
        {
            puts("0.0");
            continue;
        }
        double ans=0;
        for(int i=0; i<m; i++)
            ans+=Direction(g[i],g[(i+1)%m],p[0]);
        ans=ans<0?-ans/2:ans/2;
        printf("%.1f\n",ans);
    }
    return 0;
}


目录
相关文章
|
人工智能 算法 BI
poj 2192 Zipper
题目链接:http://poj.org/problem?id=2192 Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 18658   Accepted: 6651 Description Given ...
976 0
|
人工智能 BI
poj-3185-开关问题
描述   牛一行20他们喝的水碗。碗可以那么(面向正确的为清凉水)或颠倒的(一个位置而没有水)。他们希望所有20个水碗那么,因此用宽鼻子翻碗。   嘴太宽,他们不仅翻转一碗还碗的碗两侧(总共三个或三个——在两端的情况下碗——两碗)。
811 0
POJ 2487 Stamps
Description Background Everybody hates Raymond. He’s the largest stamp collector on planet earth and because of that he always makes fun of all the others at the stamp collector parties.
1062 0
|
机器学习/深度学习