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;
}



目录
相关文章
poj 2299 求逆序数
http://poj.org/problem?id=2299 #include using namespace std; int aa[500010],bb[500010]; long long s=0; void merge(int l,int m,int r) { ...
793 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
POJ 2027 No Brainer
Problem Description Zombies love to eat brains. Yum. Input The first line contains a single integer n indicating the number of data sets.
866 0
|
机器学习/深度学习 算法
|
算法 数据建模 机器学习/深度学习
poj1273Drainage Ditches
1 #include 2 /* 3 题意:就是寻找从源点到汇点的最大流! 4 要注意的是每两个点的流量可能有多个,也就是说有重边,所以要把两个点的所有的流量都加起来 5 就是这两个点之间的流量了! 6 ...
851 0