Hdu 3692 Shade of Hallelujah Mountain (三维空间点的旋转和投影二维凸包)

不念不忘少年蓝@ 2022-09-17 05:25 96阅读 0赞

题意：在三维空间中，给出点光源，空间中存在一个凸物体，问物体在一个给定的平面内的影子的大小。

整体做法基本都自己想出来了，被坐标旋转卡住了。。。

以下两篇博文分析地很好，我用了第一篇的方法，第二篇的方法也值得学习。

[hdu 3692 Shade of Hallelujah Mountain - 小白菜又菜 - 博客频道 - CSDN.NET][hdu 3692 Shade of Hallelujah Mountain - _ - _ - CSDN.NET]

[HDU 3692 Shade of Hallelujah Mountain （计算几何，三维空间点的旋转，二维凸包） - kuangbin - 博客园][HDU 3692 Shade of Hallelujah Mountain _ - kuangbin -]

#include <cmath>
    #include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    const int N=105;
    const double eps=1e-8;
    
    struct plane
    {
        double a,b,c,d;
        bool Get ()
        {
            scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
            if (a || b || c || d)
                return true;
            return false;
        }
    }Pl;
    
    struct point3
    {
        double x,y,z;
    
        point3(){}
        point3(double _x,double _y,double _z)
        {x=_x;y=_y;z=_z;}
    
        void Get ()
        {scanf("%lf%lf%lf",&x,&y,&z);}
    }data[N];
    
    /二维凸包部分...........
    
    struct Point  //点,向量
    {
        double x,y;
    
        int DB (double dx)  //判0函数
        {
            if(fabs(dx)<eps) return 0;
            return dx>0?1:-1;
        }
        //调用点a的该函数
        //返回1点a在向量bc的左侧
        //返回-1点a在向量bc的右侧
        //返回0点a在向量bc这条直线上
        int Cross (Point b,Point c)
        {return DB((b.x-x)*(c.y-y)-(c.x-x)*(b.y-y));}
    
        double GetTriArea (Point b,Point c)
        {return ((b.x-x)*(c.y-y)-(c.x-x)*(b.y-y))/2.0;}
    
        bool operator < (const Point &b)const //用于排序
        {
            if (fabs(y-b.y)<eps) return x-b.x<0;
            return y-b.y<0;
        }
    }pt[N],ch[N];
    
    //求凸包函数
    //pt:所有的点，n个,pt[0]到pt[n-1]
    //ch:求完的凸包中的点，len个,q[0]到q[len-1]
    void Graham (Point pt[],Point ch[],int &len,int n)      //只保存凸包顶点
    {
        int i,top=1;
        sort(pt,pt+n);
        ch[0]=pt[0];
        ch[1]=pt[1];
        for (i=2;i<n;i++)
        {
            while (top>0 && ch[top-1].Cross(ch[top],pt[i]) <= 0)
                top--;
            ch[++top]=pt[i];
        }
        int temp=top;
        for (i=n-2;i>=0;i--)
        {
            while (top>temp && ch[top-1].Cross(ch[top],pt[i]) <= 0)
                top--;
            ch[++top]=pt[i];
        }
        len=top;
    }
    
    
    
    //计算点在平面上的投影
    int Shadow (plane p, point3 s, int n )
    {//参数：平面，光源，点数
        //求出过s平行于plane的平面 ax+by+cz=D
        double D = p.a*s.x+p.b*s.y+p.c*s.z;
        if (D-p.d < 0)
        {//调整方向
            p.a *= -1;p.b *= -1;
            p.c *= -1;p.d *= -1;
            D *= -1;
        }
    
        //判断点与面的关系
        int cnt=0,i;
        for (i=0;i<n;i++)
        {//如果存在影子并且面积为有限值，则所有点应在光源与平面之间
            double det=p.a*data[i].x+p.b*data[i].y+p.c*data[i].z-D;
            if (det<0) cnt++;
        }
        if (cnt==0) return 0;
        if (cnt!=n) return n+1;
        for (i=0;i<n;i++) //计算各点与光源的连线与平面的交点
        {//先求方向向量
            double dx=data[i].x-s.x;
            double dy=data[i].y-s.y;
            double dz=data[i].z-s.z;
            //可得点集(也就是直线) (x,y,z)+t(dx,dy,dz)
            //将其带入到平面方程即可解出t，进而求出交点
            double t=(p.d-p.a*s.x-p.b*s.y-p.c*s.z)/(p.a*dx+p.b*dy+p.c*dz);
            data[i].x=s.x+t*dx;
            data[i].y=s.y+t*dy;
            data[i].z=s.z+t*dz;
        }
        return n;
    }
    
    //坐标系旋转，到x-y平面
    void change ( plane p, int n )
    {
        //平行于x-y平面的不用计算，也不能计算（分母为0）
        if  ( p.a*p.a + p.b*p.b == 0 ) return;
        point3 temp;
        for (int i=0;i<n;i++)
        {
            //绕z轴旋转
            double cosC=p.b/sqrt(p.a*p.a+p.b*p.b);
            double sinC=p.a/sqrt(p.a*p.a+p.b*p.b);
            temp.x = data[i].x*cosC-data[i].y*sinC;
            temp.y = data[i].x*sinC+data[i].y*cosC;
            temp.z = data[i].z;
            data[i] = temp;
    
            //绕x轴旋转
            double cosA=p.c/sqrt(p.a*p.a+p.b*p.b+p.c*p.c);
            double sinA=sqrt(p.a*p.a+p.b*p.b)/sqrt(p.a*p.a+p.b*p.b+p.c*p.c);
            temp.x = data[i].x;
            temp.y = data[i].y*cosA-data[i].z*sinA;
            temp.z = data[i].y*sinA+data[i].z*cosA;
            data[i] = temp;
        }
    }
    
    //计算二维凸包面积
    double crossproduct ( Point a, Point b, Point c )
    {
        return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
    }
    
    void Deal (int n)
    {
        change (Pl,n);
        for (int i=0;i<n;i++)
        {
            pt[i].x=data[i].x;
            pt[i].y=data[i].y;
        }
        int len;
        Graham (pt,ch,len,n);
        double area=0;  //计算面积
        for (int i=2;i<len;i++)
    //      area += crossproduct( ch[0], ch[i-1], ch[i] );
            area+=ch[0].GetTriArea(ch[i-1],ch[i]);
        printf("%.2lf\n",area);
    }
    
    int main ()
    {
    #ifdef ONLINE_JUDGE
    #else
    	freopen("read.txt","r",stdin);
    #endif
        while (Pl.Get())
        {
            int n,i;
            scanf("%d",&n);
            for (i=0;i<=n;i++)
                data[i].Get();
            int flag=Shadow(Pl,data[n],n);
            if (flag==0) printf("0.00\n");
            else if (flag>n) printf("Infi\n");
            else Deal (n);
        }
    	return 0;
    }

[hdu 3692 Shade of Hallelujah Mountain - _ - _ - CSDN.NET]: http://blog.csdn.net/mobius_strip/article/details/8301637
[HDU 3692 Shade of Hallelujah Mountain _ - kuangbin -]: http://www.cnblogs.com/kuangbin/archive/2012/11/06/2757150.html