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



目录
相关文章
|
算法 C++
单源最短路的建图
单源最短路的建图
45 0
|
Python
LeetCode每日一题——883. 三维形体投影面积
在 n x n 的网格 grid 中,我们放置了一些与 x,y,z 三轴对齐的 1 x 1 x 1 立方体。
123 0
LeetCode每日一题——883. 三维形体投影面积
|
人工智能
poj 1328 【Radar Installation】【几何转化、区间覆盖】
点击打开题目 Radar Installation Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 54970   Accepted: 12381 Descrip...
1078 0
|
算法
计算几何 : 凸包学习笔记 --- Graham 扫描法
凸包 (只针对二维平面内的凸包) 一、定义 简单的说,在一个二维平面内有n个点的集合S,现在要你选择一个点集C,C中的点构成一个凸多边形G,使得S集合的所有点要么在G内,要么在G上,并且保证这个凸多边形的面积最小,我们要求的就是这个C集合。
1897 0
|
机器学习/深度学习