Description

H 公司生产了一种金属制品, 是由一些笔直的金属条支撑起来的, 金属条和别的金属条在交点上被焊接在了一起. 现在由于美观需要, 在这个产品用一层特殊的材料包裹起来. 公司为了节约成本, 希望消耗的材料最少 (不计裁剪时的边角料的损失). 你的程序需要根据给定的输入, 给出符合题意的输出: 输入包括该产品的顶点的个数, 以及所有顶点的坐标; 你需要根据输入的计算出包裹这个产品所需要的材料的最小面积. 结果要求精确到小数点后第六位. (四舍五入)

Input

第 \(1\) 行是一个整数 \(n (4 \leq n \leq 100)\), 表示顶点的个数;

第 \(2\) 行到第 \(n+1\) 行, 每行是 \(3\) 个实数 \(x_i, y_i, z_i\), 表示第 \(i\) 个顶点的坐标. 每个顶点的位置各不相同.

Output

输出只有一个实数, 表示包裹一个该产品所需的材料面积的最小值.

Sample Input

4
0 0 0
1 0 0
0 1 0
0 0 1

Sample Output

2.366025

Explanation

有个做法叫随机增量法, 本来是设计到二维上应用的, 但是可以推广到 \(n\) 维.

  1. 按照输入顺序将点加入点集;
  2. 维护当前点集的凸包, 方法如下:
    1. 新点在凸包内部
      • \(O(n)\) 判定
    2. 新点在凸包外部
      • 删除从新点可见的凸包边
      • 用链表维护凸包
      • \(O(n)\) 删除和判断
  3. 是一个时间复杂度为 \(O(n^2)\) 的在线算法

如果要推广到立体几何就可以把面换成体、线换成面, 不用链表维护即可.

另外增量法需要对所有坐标进行微小的抖动, 以免出现坐标冲突.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>

using namespace std;
typedef long long lli;
typedef long double llf;
const int maxn = 210;
const llf epsilon = 1e-9;

template <typename _T>
_T sqr(_T a) { return a * a; }

llf rand_eps(void) {
    return ((llf)rand() / (llf)RAND_MAX + 0.5) * epsilon; }

struct point {
    llf x, y, z;
    point(void) {
        x = y = z = 0.0; }
    point(llf _1, llf _2, llf _3) {
        x = _1, y = _2, z = _3; }
    llf length(void) {
        return sqrt(sqr(x) + sqr(y) + sqr(z)); }
}; point operator - (point a, point b) {
    return point(a.x - b.x, a.y - b.y, a.z - b.z);
} point cross(point a, point b) {
    return point(a.y*b.z - b.y*a.z, a.z*b.x - b.z*a.x, a.x*b.y - b.x*a.y);
} point cross(point a, point b, point c) {
    return cross(b - a, c - a);
} llf dot(point a, point b) {
    return a.x*b.x + a.y*b.y + a.z*b.z;
} point add_noise(point a) {
    return point(a.x + rand_eps(), a.y + rand_eps(), a.z + rand_eps());
}

struct face {
    int v[3];
    face(void) {
        v[0] = v[1] = v[2] = 0;
    } face(int _1, int _2, int _3) {
        v[0] = _1; v[1] = _2; v[2] = _3;
    } point normal(point p[]) {
        return cross(p[v[0]], p[v[1]], p[v[2]]);
    } bool cansee(point p[], int i) {
        return dot(p[i] - p[v[0]], this->normal(p)) > 0;
    } llf area(point p[]) {
        return 0.5 * cross(p[v[0]], p[v[1]], p[v[2]]).length();
    }
};

class ConvexHull
{
public:
    point p[maxn], p1[maxn];
    bool vis[maxn][maxn];
    int n;
    vector<face> vec;
    void increment(point p[])
    {
        memset(vis, 0, sizeof(vis));
        // Generating noise in hope of distinction
        for (int i = 0; i < n; i++)
            p[i] = add_noise(p[i]);
        // Initial elements
        vec.clear();
        vec.push_back(face(0, 1, 2));
        vec.push_back(face(2, 1, 0));
        // Increment algorithm
        for (int i = 3; i < n; i++) {
            vector<face> tmp;
            tmp.clear();
            for (unsigned int j = 0; j < vec.size(); j++) {
                face f = vec[j];
                bool r = f.cansee(p, i);
                if (!r) tmp.push_back(f);
                // Marking visited
                for (int k = 0; k < 3; k++)
                    vis[f.v[k]][f.v[(k+1)%3]] = r;
            }
            for (unsigned int j = 0; j < vec.size(); j++) {
                for (int k = 0; k < 3; k++) {
                    int a = vec[j].v[k],
                        b = vec[j].v[(k+1)%3];
                    if (vis[a][b] != vis[b][a] && vis[a][b])
                        tmp.push_back(face(a, b, i));
                }
            }
            vec = tmp;
        }
        return ;
    }
    llf eval(void)
    {
        for (int i = 0; i < n; i++)
            p1[i] = p[i];
        increment(p1);
        llf res = 0.0;
        for (unsigned int i = 0; i < vec.size(); i++)
            res += vec[i].area(p);
        return res;
    }
} cvh;

int n;

int main(int argc, char** argv)
{
    scanf("%d", &n);
    cvh.n = n;
    // We are counting from 0 because 1 is hard to deal with modulo calculations
    for (int i = 0; i < n; i++)
        scanf("%Lf%Lf%Lf", &cvh.p[i].x, &cvh.p[i].y, &cvh.p[i].z);
    llf res = cvh.eval();
    printf("%.6Lf\n", res);
    return 0;
}