HDU 4449 Building Design 제3 7 회 ACM / ICPC 금화 지구 H 문제 (계산 기하학, 3 차원 볼록 + 공간 좌표 회전 + 2 차원 볼록)

Building Design
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 431    Accepted Submission(s): 117
Problem Description
You are a notable architect.
Recently, a company invites you to design their new building for them. It is not an easy task, because they make some strange claims to the new building:
1.Its shape should be the same as a convex polyhedron which they have given to you, though you can rotate it arbitrarily.
2.One face of the building should cling to the ground. (Of course! Have you ever seen a building only touch the ground by an edge, or a point, or even suspend in the air?)
3.They want the building to be as striking as possible. We call the highest point of the building as the “peak”. The higher the peak is the more striking the building will be.
4.If there are many designs meet all claims above, the occupied land of the building should be less. In another word, the building's vertical projection area on the ground should be as small as possible.
Now, give you the relative positions of vertices of the building, please design the building and tell them H – the height of the peak, as well as S - the projection area of the building in your best design.
 
 
Input
There are several test cases in the input.
Each test case begins with one integer n (1 ≤ n ≤ 50), indicating the number of vertices of the building.
Then n lines follow. Each line contains three integers x, y, z (-10000 ≤ x, y, z ≤ 10000), separated by spaces, indicating the relative positions of one vertex of the building.
The input ends with n = 0.
 
 
Output
For each test case, output two float numbers H and S in one line, separated by one space.
Please round the results to three digits after decimal point.
 
 
Sample Input
6 1 0 0 -1 0 0 0 1 0 0 -1 0 0 0 1 0 0 -1 0
 
 
Sample Output
1.155 1.732
 
 
Source
2012 Asia JinHua Regional Contest
 
 
Recommend
zhuyuanchen520
 
 
 
제목 은 바로 돌출 다 면 문 제 를 주 는 것 이다.
이 돌출 다 면 체 를 바닥 에 내 려 놓 고 한 면 이 바닥 에 닿 아야 한다.
하나의 방 법 을 구하 여 최고점 이 가장 높 고 최고점 이 같 을 때 투영 면적 을 가장 작 게 한다.출력 최고점 높이 H 와 투영 면적 S.
 
먼저 3 차원 볼록 가방 으로 모든 삼각형 표면 을 구하 세 요.
그 다음 에 모든 표면 을 매 거 하여 좌 표를 바 꾸 고 회전 시 켜 이 표면 을 수평 으로 만 든 다음 에 투영 면적 을 구하 고 가장 높 은 높이 를 계산한다.
 
제목 의 데 이 터 는 n = 1, 2, 3 이 없 는 것 같 습 니 다. 무시 할 수 있 습 니 다.
문 제 는 회전 후의 z 좌표 값 에 따라 높이 를 계산 하면 정밀도 차이 가 크다 는 것 이다.가장 좋 은 것 은 직접 면 까지 의 거 리 를 계산 하 는 것 이다.
 

//============================================================================

// Name        : Building.cpp

// Author      : kuangbin

// Version     :

// Copyright   : Your copyright notice

// Description : HDU 4449

//       +    +        

//============================================================================



#include <iostream>

#include <string.h>

#include <math.h>

#include <algorithm>

#include <stdio.h>

#include <vector>

#include <map>

#include <set>

#include <queue>

using namespace std;

const int MAXN = 110;

const double eps=1e-8;

const double PI=acos(-1.0);

inline int sign(double p)

{

    if(p>eps)return 1;

    else if(p<-eps)return -1;

    else return 0;

}

struct Point

{

    double x,y,z;

    Point(double xx=0,double yy=0,double zz=0):x(xx),y(yy),z(zz){}

    Point operator +(const Point p1)

    {

        return Point(x+p1.x,y+p1.y,z+p1.z);

    }

    Point operator -(const Point p1)

    {

        return Point(x-p1.x,y-p1.y,z-p1.z);

    }

    Point operator *(const Point p1)

    {

        return Point(y*p1.z-z*p1.y,z*p1.x-x*p1.z,x*p1.y-y*p1.x);

    }

    Point operator *(double d)

    {

        return Point(d*x,d*y,d*z);

    }

    Point operator /(double d)

    {

        return Point(x/d,y/d,z/d);

    }

    double operator ^(const Point p1)

    {

        return x*p1.x+y*p1.y+z*p1.z;

    }

    double getLen()

    {

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

    }

    void read()

    {

        scanf("%lf%lf%lf",&x,&y,&z);

    }

};

struct face

{

    int a,b,c;

    bool ok;

};



struct CH3D

{

    int n;//     

    Point P[MAXN];//    

    int num;//          

    face F[8*MAXN];//        

    int g[MAXN][MAXN];

    double vlen(Point a)

    {

        return sqrt(a.x*a.x+a.y*a.y+a.z*a.z);

    }

    Point cross(Point a,Point b,Point c)

    {

        return Point(

                (b.y-a.y)*(c.z-a.z)-(b.z-a.z)*(c.y-a.y),

                (b.z-a.z)*(c.x-a.x)-(b.x-a.x)*(c.z-a.z),

                (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x)

                );

    }

    //     *2

    double area(Point a,Point b,Point c)

    {

        return vlen((b-a)*(c-a));

    }

    //     *6

    double volume(Point a,Point b,Point c,Point d)

    {

        return ((b-a)*(c-a))^(d-a);

    }

    double dblcmp(Point &p,face &f)

    {

        Point m=P[f.b]-P[f.a];

        Point n=P[f.c]-P[f.a];

        Point t=p-P[f.a];

        return (m*n)^t;

    }

    void deal(int p,int a,int b)

    {

        int f=g[a][b];

        face add;

        if(F[f].ok)

        {

            if(dblcmp(P[p],F[f])>eps)

                dfs(p,f);

            else

            {

                add.a=b;

                add.b=a;

                add.c=p;

                add.ok=true;

                g[p][b]=g[a][p]=g[b][a]=num;

                F[num++]=add;

            }

        }

    }

    void dfs(int p,int now)

    {

        F[now].ok=false;

        deal(p,F[now].b,F[now].a);

        deal(p,F[now].c,F[now].b);

        deal(p,F[now].a,F[now].c);

    }

    bool same(int s,int t)

    {

        Point &a=P[F[s].a];

        Point &b=P[F[s].b];

        Point &c=P[F[s].c];

        return fabs(volume(a,b,c,P[F[t].a]))<eps &&

               fabs(volume(a,b,c,P[F[t].b]))<eps &&

               fabs(volume(a,b,c,P[F[t].c]))<eps;

    }



    void create()

    {

        int i,j,tmp;

        face add;

        num=0;

        if(n<4)return;



        bool flag=true;

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

        {

            if(vlen(P[0]-P[i])>eps)

            {

                swap(P[1],P[i]);

                flag=false;

                break;

            }

        }

        if(flag)return;

        flag=true;

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

        {

            if(vlen((P[0]-P[1])*(P[1]-P[i]))>eps)

            {

                swap(P[2],P[i]);

                flag=false;

                break;

            }

        }

        if(flag)return;

        flag=true;

        for(i=3;i<n;i++)

        {

            if(fabs((P[0]-P[1])*(P[1]-P[2])^(P[0]-P[i]))>eps)

            {

                swap(P[3],P[i]);

                flag=false;

                break;

            }

        }

        if(flag)return;



        for(i=0;i<4;i++)

        {

            add.a=(i+1)%4;

            add.b=(i+2)%4;

            add.c=(i+3)%4;

            add.ok=true;

            if(dblcmp(P[i],add)>0)swap(add.b,add.c);

            g[add.a][add.b]=g[add.b][add.c]=g[add.c][add.a]=num;

            F[num++]=add;

        }

        for(i=4;i<n;i++)

        {

            for(j=0;j<num;j++)

            {

                if(F[j].ok && dblcmp(P[i],F[j])>eps)

                {

                    dfs(i,j);

                    break;

                }

            }

        }

        tmp=num;

        for(i=num=0;i<tmp;i++)

            if(F[i].ok)

                F[num++]=F[i];

    }

    double ptoface(Point p,int i)

    {

         return fabs(volume(P[F[i].a],P[F[i].b],P[F[i].c],p)/vlen((P[F[i].b]-P[F[i].a])*(P[F[i].c]-P[F[i].a])));

    }



};

CH3D hull;

Point ps[MAXN];

int n;

inline Point get_point(Point st,Point ed,Point tp)

{

    double t1=(tp-st)^(ed-st);

    double t2=(ed-st)^(ed-st);

    double t=t1/t2;

    Point ans=st + ((ed-st)*t);

    return ans;

}

inline double dist(Point st,Point ed)

{

    return sqrt((ed-st)^(ed-st));

}

Point rotate(Point st,Point ed,Point tp,double A)

{

    Point root=get_point(st,ed,tp);

    Point e=(ed-st)/dist(ed,st);

    Point r=tp-root;

    Point vec=e*r;

    Point ans=r*cos(A)+vec*sin(A)+root;

    return ans;

}



struct point

{

    double x,y;

};

point list[MAXN];

int stack[MAXN],top;

double cross(point p0,point p1,point p2)

{

    return (p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x);

}

double dis(point p1,point p2)

{

    return sqrt((p2.x-p1.x)*(p2.x-p1.x)+(p2.y-p1.y)*(p2.y-p1.y));

}

bool cmp(point p1,point p2)

{

    double tmp=cross(list[0],p1,p2);

    if(sign(tmp)>0)return true;

    else if(sign(tmp)==0 && dis(list[0],p1)<dis(list[0],p2))return true;

    else return false;

}

void init(int n)

{

    point p0;

    p0=list[0];

    int k=0;

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

    {

        if( (p0.y+eps > list[i].y) || ( sign(p0.y-list[i].y)==0 && (p0.x+eps > list[i].x)))

        {

            p0=list[i];

            k=i;

        }

    }

    list[k]=list[0];

    list[0]=p0;

    sort(list+1,list+n,cmp);

}

void graham(int n)

{

    init(n);

    if(n==1)

    {

        top=0;

        stack[0]=0;

        return;

    }

    if(n==2)

    {

        top=1;

        stack[0]=0;

        stack[1]=1;

        return;

    }

    for(int i=0;i<=1;i++)stack[i]=i;

    top=1;

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

    {

        while(top>0 && cross(list[stack[top-1]],list[stack[top]],list[i])<=eps)

            top--;

        top++;

        stack[top]=i;

    }

}



bool input()

{

    scanf("%d",&n);

    if(n==0)return false;



    hull.n=n;

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

        hull.P[i].read();

    return true;

}



void solve()

{

    double ansH=0,ansS=1e200;

    double H,S;

    if(n<=2)//            

    {

        printf("0.000 0.000
");

        return;

    }

    if(n==3)//            

    {

        ansH=0;

        ansS=(hull.P[1]-hull.P[0])^(hull.P[2]-hull.P[0]);

        ansS/=2.0;

        printf("%.3lf %.3lf
",ansH,ansS);

        return;

    }

    hull.create();

    for(int i=0;i< hull.num;i++)

    {

        for(int j=0;j<n;j++)ps[j]=hull.P[j];

        Point p1=(ps[hull.F[i].b]-ps[hull.F[i].a])*(ps[hull.F[i].c]-ps[hull.F[i].a]);

        Point e(0,0,1);

        Point vec=p1*e;

        double A=p1^e/p1.getLen();

        A=acos(A);



        if(sign(A)!=0 && sign(A-PI)!=0)

        {

            Point p0(0,0,0);

            for(int j=0;j<n;j++)

                ps[j]=rotate(p0,vec,ps[j],A);

        }

        double tt=ps[hull.F[i].a].z;

        for(int j=0;j<n;j++)

            ps[j].z -= tt;

        H=0;

        for(int j=0;j<n;j++)

        {

            //H=max(H,fabs(ps[j].z)+0.00001);//      ，   WA

            H=max(H,hull.ptoface(hull.P[j],i));

            //if( fabs(hull.ptoface(hull.P[j],i)-fabs(ps[j].z))>=0.00000005)while(1);

            //         ，        ，         WA

        }



        //for(int j=0;j<n;j++)

        //    H=max(H,hull.ptoface(hull.P[j],i));

        for(int j=0;j<n;j++)

        {

           list[j].x=ps[j].x;

           list[j].y=ps[j].y;

        }

        graham(n);

        S=0;

        for(int j=0;j<top;j++)

            S+=(list[stack[j]].x*list[stack[j+1]].y - list[stack[j]].y*list[stack[j+1]].x);

        S+=(list[stack[top]].x*list[stack[0]].y - list[stack[top]].y*list[stack[0]].x);

        S=fabs(S);

        S/=2;

        if(H > ansH || ( sign(H-ansH)==0 && ansS > S ))

        {

           ansH=H;

           ansS=S;

        }

    }

    printf("%.3lf %.3lf
",ansH,ansS);

}



int main()

{

    while(input())solve();

    return 0;

}