Day 014-Q5 — 凸多面体の体積計算（3D 幾何）

問題

3次元空間 N 点の凸包の表面積と体積を求めよ。

制約

入出力例

8
0 0 0
1 0 0
0 1 0
1 1 0
0 0 1
1 0 1
0 1 1
1 1 1

6.000000
1.000000

ヒント (段階的開示)

模範解答 (Python)

📋 コピーimport sys
from math import sqrt

EPS = 1e-9

def cross3(a, b):
    return (a[1]*b[2] - a[2]*b[1],
            a[2]*b[0] - a[0]*b[2],
            a[0]*b[1] - a[1]*b[0])

def dot3(a, b):
    return a[0]*b[0] + a[1]*b[1] + a[2]*b[2]

def sub3(a, b):
    return (a[0]-b[0], a[1]-b[1], a[2]-b[2])

def norm3(a):
    return sqrt(a[0]**2 + a[1]**2 + a[2]**2)

def signed_vol(a, b, c):
    return dot3(a, cross3(b, c))

def visible(face_pts, p, pts):
    a, b, c = pts[face_pts[0]], pts[face_pts[1]], pts[face_pts[2]]
    n = cross3(sub3(b, a), sub3(c, a))
    return dot3(n, sub3(p, a)) > EPS

def convex_hull_3d(pts):
    n = len(pts)
    faces = []
    init = list(range(4))
    a, b, c, d = [pts[i] for i in init]
    if dot3(cross3(sub3(b,a), sub3(c,a)), sub3(d,a)) > 0:
        init[0], init[1] = init[1], init[0]
    a, b, c, d = init
    faces = [[a, b, c], [a, c, d], [a, d, b], [b, d, c]]
    for i in range(4, n):
        p = pts[i]
        visible_faces = [f for f in faces if visible(f, p, pts)]
        if not visible_faces:
            continue
        horizon = []
        edge_count = {}
        for f in visible_faces:
            for e in [(f[0],f[1]), (f[1],f[2]), (f[2],f[0])]:
                key = tuple(sorted(e))
                edge_count[key] = edge_count.get(key, 0) + 1
        for f in visible_faces:
            for e in [(f[0],f[1]), (f[1],f[2]), (f[2],f[0])]:
                key = tuple(sorted(e))
                if edge_count[key] == 1:
                    horizon.append(e)
        faces = [f for f in faces if not visible(f, p, pts)]
        for e in horizon:
            new_face = [e[0], e[1], i]
            faces.append(new_face)
    return faces

def solve():
    n = int(input())
    pts = []
    for _ in range(n):
        x, y, z = map(int, input().split())
        pts.append((x, y, z))
    faces = convex_hull_3d(pts)
    surface_area = 0.0
    volume_6x = 0.0
    for f in faces:
        a, b, c = pts[f[0]], pts[f[1]], pts[f[2]]
        ab = sub3(b, a); ac = sub3(c, a)
        n_vec = cross3(ab, ac)
        surface_area += norm3(n_vec) / 2.0
        volume_6x += signed_vol(a, b, c)
    volume = abs(volume_6x) / 6.0
    print(f"{surface_area:.6f}")
    print(f"{volume:.6f}")

solve()

Step-by-Step 解説

よくあるミス

次のステップ

• Minkowski 和（3Dグラフ + 凸幾何）

自己評価

自分の回答

気づき・メモ