POJ 3528 & POJ 2974 三维凸包

题意：给出n个点，求三维凸包及其表面积。

下面这个模板从NOI选手的资料中拿到的，特别短，用的是卷包裹法，不过貌似必须保证四点不共面，要不就会出错。

POJ 3528

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
#include<vector>
#include<map>
#include<cmath>
#define maxn 1000
using namespace std;
struct point
{
    double x,y,z;
    point() {}
    point(double _x,double _y,double _z):x(_x),y(_y),z(_z) {}
};
point operator-(const point &a,const point &b)
{
    return point(a.x-b.x,a.y-b.y,a.z-b.z);
}
double operator*(const point &a,const point &b)
{
    return a.x*b.x+a.y*b.y+a.z*b.z;
}
point operator^(const point &a,const point &b)
{
    return point(a.y*b.z-a.z*b.y,a.z*b.x-a.x*b.z,a.x*b.y-a.y*b.x);
}
double Volcume(const point &a,const point &b,const point &c,const point &d)
{
    return ((b-a)^(c-a))*(d-a);
}
set<pair<int,int> >myset;
vector<pair<int, pair<int,int> > >faces;
point data[maxn];
int n;
void wrap(int a,int b)
{
    if(myset.find(make_pair(a,b))==myset.end())
    {
        int c=-1;
        for(int i=0; i<n; i++)
            if(i!=a&&i!=b)
            {
                if(c==-1||Volcume(data[c],data[a],data[b],data[i])>0)
                    c=i;
            }
        if(c!=-1)
        {
            faces.push_back(make_pair(a,make_pair(b,c)));
            myset.insert(make_pair(a,b));
            myset.insert(make_pair(b,c));
            myset.insert(make_pair(c,a));
            wrap(c,b),wrap(a,c);
        }
    }
}
double sqr(double x)
{
    return x*x;
}
double dis(point a,point b)
{
    return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y)+sqr(a.z-b.z));
}
double area(point a,point b,point c)
{
    double a1=dis(b,c),b1=dis(a,c),c1=dis(a,b),t=(a1+b1+c1)/2;
    return sqrt(t*(t-a1)*(t-b1)*(t-c1));
}
int main()
{
    while(~scanf("%d",&n))
    {
        for(int i=0; i<n; i++)scanf("%lf%lf%lf",&data[i].x,&data[i].y,&data[i].z);
        for(int i=1; i<n; i++)
            if(data[i].x<data[0].x) swap(data[i],data[0]);
        for(int i=2; i<n; i++)
            if((data[i].x-data[0].x)*(data[1].y-data[0].y)>(data[i].y-data[0].y)*(data[1].x-data[0].x))
                swap(data[1],data[i]);
        wrap(0,1);
        double ans=0;
        for(int i=0; i<(int)faces.size(); i++)
            ans+=area(data[faces[i].first],data[faces[i].second.first],data[faces[i].second.second]);
        printf("%.3f\n",ans);
    }
    return 0;
}

POJ 2974

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
#include<vector>
#include<map>
#include<cmath>
#define maxn 1000
using namespace std;
struct point
{
    double x,y,z;
    point() {}
    point(double _x,double _y,double _z):x(_x),y(_y),z(_z) {}
};
point operator-(const point &a,const point &b)
{
    return point(a.x-b.x,a.y-b.y,a.z-b.z);
}
double operator*(const point &a,const point &b)
{
    return a.x*b.x+a.y*b.y+a.z*b.z;
}
point operator^(const point &a,const point &b)
{
    return point(a.y*b.z-a.z*b.y,a.z*b.x-a.x*b.z,a.x*b.y-a.y*b.x);
}
double Volcume(const point &a,const point &b,const point &c,const point &d)
{
    return ((b-a)^(c-a))*(d-a);
}
set<pair<int,int> >myset;
vector<pair<int, pair<int,int> > >faces;
point data[maxn];
int n;
void wrap(int a,int b)
{
    if(myset.find(make_pair(a,b))==myset.end())
    {
        int c=-1;
        for(int i=0; i<n; i++)
            if(i!=a&&i!=b)
            {
                if(c==-1||Volcume(data[c],data[a],data[b],data[i])>0)
                    c=i;
            }
        if(c!=-1)
        {
            faces.push_back(make_pair(a,make_pair(b,c)));
            myset.insert(make_pair(a,b));
            myset.insert(make_pair(b,c));
            myset.insert(make_pair(c,a));
            wrap(c,b),wrap(a,c);
        }
    }
}
double sqr(double x)
{
    return x*x;
}
double dis(point a,point b)
{
    return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y)+sqr(a.z-b.z));
}
double area(point a,point b,point c)
{
    double a1=dis(b,c),b1=dis(a,c),c1=dis(a,b),t=(a1+b1+c1)/2;
    return sqrt(t*(t-a1)*(t-b1)*(t-c1));
}
int main()
{
    while(~scanf("%d",&n),n)
    {
        myset.clear(),faces.clear();
        for(int i=0; i<n; i++)scanf("%lf%lf%lf",&data[i].x,&data[i].y,&data[i].z);
        for(int i=1; i<n; i++)
            if(data[i].x<data[0].x) swap(data[i],data[0]);
        for(int i=2; i<n; i++)
            if((data[i].x-data[0].x)*(data[1].y-data[0].y)>(data[i].y-data[0].y)*(data[1].x-data[0].x))
                swap(data[1],data[i]);
        wrap(0,1);
        double ans=0;
        for(int i=0; i<(int)faces.size(); i++)
            ans+=area(data[faces[i].first],data[faces[i].second.first],data[faces[i].second.second]);
        printf("%.0f\n",ans);
    }
    return 0;
}