Description
H公司生产了一种金属制品，是由一些笔直的金属条支撑起来的，金属条和别的金属条在交点上被焊接在了一起。现在由于美观需要，在这个产品用一层特殊的材料包裹起来。公司为了节约成本，希望消耗的材料最少（不计裁剪时的边角料的损失）。你的程序需要根据给定的输入，给出符合题意的输出： 输入包括该产品的顶点的个数，以及所有顶点的坐标； 你需要根据输入的计算出包裹这个产品所需要的材料的最小面积。 结果要求精确到小数点后第六位。（四舍五入）
Input
第1行是一个整数n(4 <= n <= 100)，表示顶点的个数；第2行到第n+1行，每行是3个实数xi,yi,zi，表示第i个顶点的坐标。每个顶点的位置各不相同。
Output
输出只有一个实数，表示包裹一个该产品所需的材料面积的最小值。
Sample Input
4
0 0 0
1 0 0
0 1 0
0 0 1 说明：该输入示例中共有4个点，可参见后面的图示。
Sample Output
2.366025
裸的三维凸包，板子题
#include <iostream>#include <cmath>#include <algorithm>#include <cstdio>#include <cstring>#include <string>#include <vector>#include <map>#include <functional>#include <cstdlib>#include <queue>#include <stack>using namespace std;#define For(i,n) for(int i=1;i<=n;i++)#define Fork(i,k,n) for(int i=k;i<=n;i++)#define Rep(i,n) for(int i=0;i<n;i++)#define ForD(i,n) for(int i=n;i;i--)#define ForkD(i,k,n) for(int i=n;i>=k;i--)#define RepD(i,n) for(int i=n;i>=0;i--)#define Forp(x) for(int p=PRe[x];p;p=Next[p])#define Forpiter(x) for(int &p=iter[x];p;p=Next[p]) #define Lson (o<<1)#define Rson ((o<<1)+1)#define MEM(a) memset(a,0,sizeof(a));#define MEMI(a) memset(a,127,sizeof(a));#define MEMi(a) memset(a,128,sizeof(a));#define INF (2139062143)#define F (100000007)#define pb push_back#define mp make_pair #define fi first#define se second#define vi vector<int> #define pi pair<int,int>#define SI(a) ((a).size())#define Pr(kcase,ans) printf("Case #%d: %lld/n",kcase,ans);#define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl;#define PRi2D(a,n,m) For(i,n) { / For(j,m-1) cout<<a[i][j]<<' ';/ cout<<a[i][m]<<endl; / } #pragma comment(linker, "/STACK:102400000,102400000")typedef long long ll;typedef double ld;typedef unsigned long long ull;ll mul(ll a,ll b){return (a*b)%F;}ll add(ll a,ll b){return (a+b)%F;}ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;}void upd(ll &a,ll b){a=(a%F+b%F)%F;}int read(){ int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();} while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();} return x*f;}ll sqr(ll a){return a*a;}double sqr(double a){return a*a;}ld PI = 3.141592653589793238462643383;const double eps=1e-11;int dcmp(double x) { if (fabs(x)<eps) return 0; else return x<0 ? -1 : 1; }struct P3{ double x,y,z; P3(double x=0,double y=0,double z=0):x(x),y(y),z(z){}}; typedef P3 V3;V3 Operator+(V3 A,V3 B) { return V3(A.x+B.x, A.y+B.y ,A.z+B.z);} V3 operator-(V3 A,V3 B) { return V3(A.x-B.x, A.y-B.y ,A.z-B.z );}V3 operator*(V3 A,double p) { return V3(A.x*p, A.y*p, A.z*p);}V3 operator/(V3 A,double p) { return V3(A.x/p, A.y/p, A.z/p);}double Dot(V3 A,V3 B) {return A.x*B.x + A.y*B.y + A.z*B.z; }double Length(V3 A) {return sqrt(Dot(A,A));}double Angle(V3 A,V3 B){return acos(Dot(A, B)) / Length(A) / Length(B); }bool operator==(const P3& a,const P3& b) { return dcmp(a.x-b.x)==0 && dcmp(a.y-b.y) == 0 && dcmp(a.z-b.z) == 0;} V3 Cross(V3 A,V3 B) { return V3(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 Area2(P3 A,P3 B,P3 C) {return Length(Cross(B-A,C-A));}struct Face{ int v[3]; V3 normal(P3 *p) const { return Cross(p[v[1]]-p[v[0]], p[v[2]]-p[v[0]]); } int cansee(P3 *p, int i) const { return Dot(p[i] - p[v[0]], normal(p))>0? 1 : 0; }};bool vis[1000][1000];vector<Face> CH3D(P3 *p, int n) { MEM(vis); vector<Face> cur; cur.pb((Face){{0,1,2}}); cur.pb((Face){{2,1,0}}); Fork(i,3,n-1) { vector<Face> next; int sz=SI(cur); Rep(j,sz) { Face &f = cur[j]; int res = f.cansee(p, i); if (!res) next.pb(f); Rep(k,3) vis[f.v[k]][f.v[(k+1)%3]] = res; } Rep(j,sz) Rep(k,3) { int a=cur[j].v[k], b=cur[j].v[(k+1)%3]; if (vis[a][b]!= vis[b][a] && vis[a][b]) { next.pb((Face) {a, b, i}); } } cur = next; } return cur;}P3 read_point3() { P3 a; scanf("%lf%lf%lf",&a.x,&a.y,&a.z); return a; }P3 p[1000];double rand01() {return rand()/(double)RAND_MAX;}double randeps() {return (rand01()-0.5)*eps; }P3 add_noise(P3 p) { return P3(p.x+randeps(),p.y+randeps(),p.z+randeps());}int main(){ // freopen("bzoj1209.in","r",stdin);// freopen(".out","w",stdout); int n=read(); Rep(i,n) p[i]= read_point3(); Rep(i,n) p[i]=add_noise(p[i]); vector<Face> vvv = CH3D(p,n); int m=SI(vvv);double S=0; Rep(i,m) { S+=Area2(p[vvv[i].v[0] ],p[vvv[i].v[1] ],p[vvv[i].v[2] ])/2; // cout<<vvv[i].v[0]<<' '<<vvv[i].v[1]<<' '<<vvv[i].v[2]<<endl; } printf("%.6lf/n",S); return 0;}新闻热点
疑难解答
