UVA 1488 Shade of Hallelujah Mountain（三维平面旋转-二维凸包）

不念不忘少年蓝@ 2022-03-29 08:46 62阅读 0赞

题目链接：[http://uva.onlinejudge.org/index.php?option=com\_onlinejudge&Itemid=8&page=show\_problem&problem=4234][http_uva.onlinejudge.org_index.php_option_com_onlinejudge_Itemid_8_page_show_problem_problem_4234]

题意：给出三维空间内一个平面A:ax+by+cz=d，一个点光源S，一个凸多面体B。求凸多面体在A上的投影面积大小。

思路：（1）若B全部在S的上方，则投影为0；若B有些顶点在S上方有些在S下方（这里上下以A作为参考标准，靠近A为下），则投影为无穷；否则投影是可以计算的；

（2）首先将A进行旋转，得到新的面A'：c'z=d，其中c'=sqrt(a\*a+b\*b+c\*c)。S和B进行同样的旋转。这里，(a,b,c)，我先将其转成(0,sqrt(a\*a+b\*b),c),接着转成(0,0,sqrt(a\*a+b\*b+c\*c))。

（3）求出B的各个点在A上投影点，然后求这些投影点的凸包，之后求凸包的面积。

int sgn(double x)  
\{   
    if(x>EPS) return 1;  
    if(x<-EPS) return -1;  
    return 0;  
\}  
  
  
struct POINT  
\{   
    int x,y;  
      
    POINT()\{\}  
    POINT(int \_x,int \_y)  
    \{   
        x=\_x;  
        y=\_y;  
    \}  
      
    void get()  
    \{   
        RD(x,y);  
    \}  
\};  
  
  
struct point  
\{   
    double x,y;  
      
          
    point()\{\}  
    point(double \_x,double \_y)  
    \{   
        x=\_x;  
        y=\_y;  
    \}  
      
    void get()  
    \{   
        RD(x); RD(y);  
    \}  
      
    point operator+(point a)  
    \{   
        return point(x+a.x,y+a.y);  
    \}  
      
    point operator-(point a)  
    \{   
        return point(x-a.x,y-a.y);  
    \}  
      
    double operator\*(point a)  
    \{   
        return x\*a.y-y\*a.x;  
    \}  
      
    point operator\*(double t)  
    \{   
        return point(x\*t,y\*t);  
    \}  
      
    double operator^(point a)  
    \{   
        return x\*a.x+y\*a.y;  
    \}  
      
    double len()  
    \{   
        return sqrt(x\*x+y\*y);  
    \}  
      
    point zhuanShun(double t)  
    \{   
        return point(x\*cos(t)+y\*sin(t),y\*cos(t)-x\*sin(t));  
    \}  
      
    point zhuanNi(double t)  
    \{   
        return point(x\*cos(t)-y\*sin(t),x\*sin(t)+y\*cos(t));  
    \}  
      
    point adjust(double L)  
    \{   
        double d=len();  
        L/=d;  
        return point(x\*L,y\*L);  
    \}  
      
    void print()  
    \{   
        printf("%.3lf %.3lf\\n",x+EPS,y+EPS);  
    \}  
\};  
  
  
double len(point a)  
\{   
    return a.len();  
\}  
  
  
struct point3  
\{   
    double x,y,z;  
      
    point3()\{\}  
    point3(double \_x,double \_y,double \_z)  
    \{   
        x=\_x;  
        y=\_y;  
        z=\_z;  
    \}  
      
    void get()  
    \{   
        cin>>x>>y>>z;  
    \}  
      
    point3 operator+(point3 a)  
    \{   
        return point3(x+a.x,y+a.y,z+a.z);  
    \}  
      
    point3 operator-(point3 a)  
    \{   
        return point3(x-a.x,y-a.y,z-a.z);  
    \}  
      
    point3 operator\*(point3 a)  
    \{   
        return point3(y\*a.z-z\*a.y,z\*a.x-x\*a.z,x\*a.y-y\*a.x);  
    \}  
      
    point3 operator\*(double t)  
    \{   
        return point3(x\*t,y\*t,z\*t);  
    \}  
      
    double operator^(point3 a)  
    \{   
        return x\*a.x+y\*a.y+z\*a.z;  
    \}  
      
    point3 operator/(double t)  
    \{   
        return point3(x/t,y/t,z/t);  
    \}  
      
    double len()  
    \{   
        return sqrt(x\*x+y\*y+z\*z);  
    \}  
      
    point3 adjust(double L)  
    \{   
        double t=len();  
        L/=t;  
        return point3(x\*L,y\*L,z\*L);  
    \}  
      
    void print()  
    \{   
        printf("%.10lf %.10lf %.10lf\\n",x+EPS,y+EPS,z+EPS);  
    \}  
\};  
  
  
  
  
double len(point3 a)  
\{   
    return a.len();  
\}  
  
  
  
  
double getArea(point3 a,point3 b,point3 c)  
\{   
    double x=len((b-a)\*(c-a));  
    return x/2;  
\}  
      
double getVolume(point3 a,point3 b,point3 c,point3 d)  
\{   
    double x=(b-a)\*(c-a)^(d-a);  
    return x/6;  
\}  
  
  
point3 pShadowOnPlane(point3 p,point3 a,point3 b,point3 c)  
\{   
    point3 v=(b-a)\*(c-a);  
    if(sgn(v^(a-p))<0) v=v\*-1;  
    v=v.adjust(1);  
    double d=fabs(v^(a-p));  
    return p+v\*d;  
\}  
  
  
double lineToLine(point3 a,point3 b,point3 p,point3 q)  
\{   
    point3 v=(b-a)\*(q-p);  
    return fabs((a-p)^v)/len(v);  
\}  
  
  
int pInPlane(point3 p,point3 a,point3 b,point3 c)  
\{   
    double S=getArea(a,b,c);  
    double S1=getArea(a,b,p);  
    double S2=getArea(a,c,p);  
    double S3=getArea(b,c,p);  
    return sgn(S-S1-S2-S3)==0;  
\}  
  
  
int opposite(point3 p,point3 q,point3 a,point3 b,point3 c)  
\{   
    point3 v=(b-a)\*(c-a);  
    double x=v^(p-a);  
    double y=v^(q-a);  
    return sgn(x\*y)<0;  
\}  
  
  
int segCrossTri(point3 p,point3 q,point3 a,point3 b,point3 c)  
\{   
    return opposite(p,q,a,b,c)&&  
            opposite(a,b,p,q,c)&&  
            opposite(a,c,p,q,b)&&  
            opposite(b,c,p,q,a);  
\}  
  
  
double pToPlane(point3 p,point3 a,point3 b,point3 c)  
\{   
    double v=((b-a)\*(c-a)^(p-a))/6;  
    double s=len((b-a)\*(c-a))/2;  
    return fabs(3\*v/s);  
\}  
  
  
  
  
double pToLine(point3 p,point3 a,point3 b)  
\{   
    double S=len((a-p)\*(b-p));  
    return S/len(a-b);  
\}  
  
  
  
  
double pToSeg(point3 p,point3 a,point3 b)  
\{   
    if(sgn((p-a)^(b-a))<=0) return len(a-p);  
    if(sgn((p-b)^(a-b))<=0) return len(b-p);  
    return pToLine(p,a,b);  
\}  
  
  
double pToPlane1(point3 p,point3 a,point3 b,point3 c)  
\{   
    point3 k=pShadowOnPlane(p,a,b,c);  
    if(pInPlane(k,a,b,c)) return pToPlane(p,a,b,c);  
    double x=pToSeg(p,a,b);  
    double y=pToSeg(p,a,c);  
    double z=pToSeg(p,b,c);  
    return min(x,min(y,z));  
\}  
  
  
  
  
double getAng(point3 a,point3 b)  
\{   
    double x=(a^b)/len(a)/len(b);  
    return acos(x);  
\}  
  
  
double segToSeg(point3 a,point3 b,point3 p,point3 q)  
\{   
    point3 v=(b-a)\*(q-p);  
      
    double A,B,A1,B1;  
    A=((b-a)\*v)^(p-a);  
    B=((b-a)\*v)^(q-a);  
      
    A1=((p-q)\*v)^(a-q);  
    B1=((p-q)\*v)^(b-q);  
    if(sgn(A\*B)<=0&&sgn(A1\*B1)<=0)   
    \{   
        return lineToLine(a,b,p,q);  
    \}  
  
  
    double x=min(pToSeg(a,p,q),pToSeg(b,p,q));  
    double y=min(pToSeg(p,a,b),pToSeg(q,a,b));  
    return min(x,y);  
\}  
  
  
struct face  
\{   
    int a,b,c,ok;  
      
    face()\{\}  
    face(int \_a,int \_b,int \_c,int \_ok)  
    \{   
        a=\_a;  
        b=\_b;  
        c=\_c;  
        ok=\_ok;  
    \}  
\};  
  
  
struct \_3DCH  
\{   
    face F\[N<<2\];  
    int b\[N\]\[N\],cnt,n;  
    point3 p\[N\];  
      
    int getDir(point3 t,face F)  
    \{   
        double x=(p\[F.b\]-p\[F.a\])\*(p\[F.c\]-p\[F.a\])^(t-p\[F.a\]);  
        return sgn(x);  
    \}  
      
      
    void deal(int i,int x,int y)  
    \{   
        int f=b\[x\]\[y\];  
        if(!F\[f\].ok) return;  
        if(getDir(p\[i\],F\[f\])==1) DFS(i,f);  
        else  
        \{   
            b\[y\]\[x\]=b\[x\]\[i\]=b\[i\]\[y\]=cnt;  
            F\[cnt++\]=face(y,x,i,1);  
        \}  
    \}  
      
    void DFS(int i,int j)  
    \{   
        F\[j\].ok=0;  
        deal(i,F\[j\].b,F\[j\].a);  
        deal(i,F\[j\].c,F\[j\].b);  
        deal(i,F\[j\].a,F\[j\].c);  
    \}  
      
    void construct()  
    \{   
        int i,j,k=0;  
        for(i=1;i<n;i++) if(sgn(len(p\[i\]-p\[0\])))  
        \{   
            swap(p\[i\],p\[1\]);  
            k++;  
            break;  
        \}  
        if(k!=1) return;  
        for(i=2;i<n;i++) if(sgn(getArea(p\[0\],p\[1\],p\[i\])))  
        \{   
            swap(p\[i\],p\[2\]);  
            k++;  
            break;  
        \}  
        if(k!=2) return;  
        for(i=3;i<n;i++) if(sgn(getVolume(p\[0\],p\[1\],p\[2\],p\[i\])))  
        \{   
            swap(p\[i\],p\[3\]);  
            k++;  
            break;  
        \}  
        if(k!=3) return;  
          
        cnt=0;  
        FOR0(i,4)  
        \{   
            face k=face((i+1)%4,(i+2)%4,(i+3)%4,1);  
            if(getDir(p\[i\],k)==1) swap(k.b,k.c);  
            b\[k.a\]\[k.b\]=b\[k.b\]\[k.c\]=b\[k.c\]\[k.a\]=cnt;  
            F\[cnt++\]=k;  
        \}  
          
        for(i=4;i<n;i++) FOR0(j,cnt)  
        \{   
            if(F\[j\].ok&&getDir(p\[i\],F\[j\])==1)  
            \{   
                DFS(i,j);  
                break;  
            \}  
        \}  
        j=0;  
        FOR0(i,cnt) if(F\[i\].ok) F\[j++\]=F\[i\];  
        cnt=j;  
    \}  
      
    point3 getCenter()  
    \{   
        point3 ans=point3(0,0,0),o=point3(0,0,0);  
        double s=0,temp;  
        int i;  
        FOR0(i,cnt)  
        \{   
            face k=F\[i\];  
            temp=getVolume(o,p\[k.a\],p\[k.b\],p\[k.c\]);  
            ans=ans+(o+p\[k.a\]+p\[k.b\]+p\[k.c\])/4\*temp;  
            s+=temp;  
        \}  
        ans=ans/s;  
        return ans;  
    \}  
      
    double getMinDis(point3 a)  
    \{   
        double ans=dinf;  
        int i;  
        FOR0(i,cnt)   
        \{   
            face k=F\[i\];  
            ans=min(ans,pToPlane(a,p\[k.a\],p\[k.b\],p\[k.c\]));  
        \}  
        return ans;  
    \}  
      
\};  
  
  
  
  
double a,b,c,d;  
int n;  
point3 p\[N\],S;  
  
  
void init()  
\{   
    if(sgn(a)==0&&sgn(b)==0) return;  
    p\[n+1\]=S;  
    double sinC,cosC;  
    int i;  
    point3 temp;  
      
    sinC=a/sqrt(a\*a+b\*b);  
    cosC=b/sqrt(a\*a+b\*b);  
    FOR1(i,n+1)   
    \{   
        temp=p\[i\];  
        p\[i\].x=temp.x\*cosC-temp.y\*sinC;  
        p\[i\].y=temp.x\*sinC+temp.y\*cosC;  
    \}  
    sinC=sqrt(a\*a+b\*b)/sqrt(a\*a+b\*b+c\*c);  
    cosC=c/sqrt(a\*a+b\*b+c\*c);  
    FOR1(i,n+1)   
    \{   
        temp=p\[i\];  
        p\[i\].y=temp.y\*cosC-temp.z\*sinC;  
        p\[i\].z=temp.y\*sinC+temp.z\*cosC;  
    \}  
    S=p\[n+1\];  
\}  
  
  
  
  
int deal()  
\{   
    double D=a\*S.x+b\*S.y+c\*S.z;  
    if(sgn(D-d)<0)  
    \{   
        a\*=-1; b\*=-1; c\*=-1; d\*=-1;  
        D\*=-1;  
    \}  
    int cnt=0,i;  
    FOR1(i,n)  
    \{   
        if(sgn(a\*p\[i\].x+b\*p\[i\].y+c\*p\[i\].z-D)<0)  
        \{   
            cnt++;  
        \}  
    \}  
    return cnt;  
\}  
  
  
point A\[N\],B\[N\];  
int Bnum;  
  
  
point get(point3 p)  
\{   
    p=p-S;  
    double t=(d/sqrt(a\*a+b\*b+c\*c)-S.z)/p.z;  
    p=S+p\*t;  
    return point(p.x,p.y);  
\}  
  
  
point H;  
  
  
int cmp(point a,point b)  
\{   
    int x=sgn((a-H)\*(b-H));  
    if(x) return x==1;  
    return sgn(len(a-H)-len(b-H))<=0;;  
\}  
  
  
int cross(point a,point b,point p)  
\{   
    return sgn((b-a)\*(p-a));  
\}  
  
  
void Graham(point p\[\],int n,point q\[\],int &m)  
\{   
    m=0;  
    if(n<3) return;  
    int i,k=0;  
    int a,b;  
    FOR0(i,n)  
    \{   
        a=sgn(p\[i\].y-p\[k\].y);  
        b=sgn(p\[i\].x-p\[k\].x);  
        if(a==-1||a==0&&b==-1) k=i;  
    \}  
    swap(p\[0\],p\[k\]); H=p\[0\]; sort(p,p+n,cmp);  
    q\[0\]=p\[0\]; q\[1\]=p\[1\]; p\[n\]=p\[0\];  
    m=2;  
    for(i=2;i<=n;i++)  
    \{   
        while(m>1&&cross(q\[m-2\],q\[m-1\],p\[i\])<=0) m--;  
        q\[m++\]=p\[i\];  
    \}  
    m--;  
\}  
  
  
double cal()  
\{   
    int i;  
    FOR1(i,n) A\[i-1\]=get(p\[i\]);  
    Graham(A,n,B,Bnum);  
    double ans=0;  
    B\[Bnum\]=B\[0\];  
    FOR1(i,Bnum) ans+=B\[i\]\*B\[i-1\];  
    return fabs(ans/2);  
\}  
  
  
int main()  
\{   
    while(scanf("%lf",&a)!=-1)  
    \{   
        RD(b,c,d);  
        if(!a&&!b&&!c&&!d) break;  
        RD(n);  
        int i;  
        FOR1(i,n) p\[i\].get();  
        S.get();  
          
        int flag=deal();  
        if(flag==0) puts("0.00");  
        else if(flag!=n) puts("Infi");  
        else   
        \{   
            init();  
            PR(cal());  
        \}  
    \}  
\}

[http_uva.onlinejudge.org_index.php_option_com_onlinejudge_Itemid_8_page_show_problem_problem_4234]: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4234