import random
from typing import List, Tuple
import math
# 浮点数的符号函数
ESP = 10 ** (-8)
def sign(val: float):
if abs(val) < ESP:
return 0
return 1 if val > 0 else -1
def vec_length_3d(v):
return math.sqrt(v[0]**2 + v[1]**2 + v[2]**2)
# 三维向量的内积, 返回点积数值, 输入a, b都是三维向量(x, y, z)
def dot3d(a, b):
return a[0]*b[0] + a[1]*b[1] + a[2]*b[2]
# 三维向量外积, 返回结果三维向量,输入a, b都是三维向量(x, y, z)
def cross3d(a, b):
x1, y1, z1 = a
x2, y2, z2 = b
return (y1 * z2 - y2 * z1, x2 * z1 - x1 * z2, x1 * y2 - x2 * y1)
# 求解a向量和b向量组成的平面的法向量,以a逆时针转到b作为右手系,法向量方向和该右手系对应
# 输入a, b均为三维向量(x, y, z), 输出也为三维向量
def normal_vec(a, b):
return cross3d(a, b)
# 判断点是否在平面法向量指向的一侧, a, b是平面上不平行的两个向量,p是平面上一个点, point是待判断的三维坐标点
# 这里法向量用的是a和b的外积向量的方向
def point_on_normal_vec_side(p, a, b, point) -> bool:
norm = normal_vec(a, b)
vv = (point[0] - p[0], point[1] - p[1], point[2] - p[2])
return dot3d(norm, vv) > 0
# 求三维空间三个点构成的三角形的面积
def area(a, b, c):
v1 = (b[0] - a[0], b[1] - a[1], b[2] - a[2])
v2 = (c[0] - a[0], c[1] - a[1], c[2] - a[2])
return vec_length_3d(cross3d(v1, v2)) / 2
class ThreeDimensionalConvex:
# 获取三维凸包函数,输入点序列,返回三维凸包中所有三角形平面的列表,每个平面以顶点逆时针(站在凸包外面看是逆时针)排列表示((x1, y1), (x2, y2), (x3, y3))
@staticmethod
def get_convex(points: List[Tuple]) -> List:
# 点数不足3个,认为没有三维凸包
if len(points) < 3:
return []
a, b, c = points[0], points[1], points[2]
v1, v2 = (b[0]-a[0], b[1]-a[1], b[2]-a[2]), (c[0]-a[0], c[1]-a[1], c[2]-a[2])
planes = set()
planes.add((a, b, c))
n = len(points)
for ii in range(3, n):
see = {} # see表示有向边a->b对应的三角形能否被看到
del_planes = set() # 要删除的平面
# 对新点做一下随机扰动,避免四点共面,让每一个面都能用三角形表示
# 避免新点在和已经有的平面上,难以判断到底是保留平面还是删除平面
new_p = (points[ii][0] + (random.random()-0.5) * (10**(-12)), points[ii][1] + (random.random()-0.5) * (10**(-12)), points[ii][2] + (random.random()-0.5) * (10**(-12)))
if ii == 3:
# 第一个平面的点的序列有可能一开始是排反的,这里要做下特判
a, b, c = planes.pop()
v1, v2 = (b[0] - a[0], b[1] - a[1], b[2] - a[2]), (c[0] - b[0], c[1] - b[1], c[2] - b[2])
if point_on_normal_vec_side(a, v1, v2, new_p):
planes.clear()
planes.add((c, b, a))
else:
planes.add((a, b, c))
flag = False
for plane in planes:
a, b, c = plane
v1, v2 = (b[0]-a[0], b[1]-a[1], b[2]-a[2]), (c[0]-b[0], c[1]-b[1], c[2]-b[2])
if point_on_normal_vec_side(a, v1, v2, new_p):
flag = True
see[(a, b)] = True
see[(b, c)] = True
see[(c, a)] = True
del_planes.add(plane)
else:
see[(a, b)] = False
see[(b, c)] = False
see[(c, a)] = False
if flag or ii == 3:
planes = planes - del_planes
for a, b in see.keys():
# 添加新的平面
if see[(a, b)] == False and ((b, a) not in see or see[(b, a)] == True):
planes.add( (b, a, new_p) )
return list(planes)
n = int(input())
points = []
for _ in range(n):
x, y, z = map(float, input().split())
points.append((x, y, z))
ret = ThreeDimensionalConvex.get_convex(points)
ans = 0
for val in ret:
ans += area(*val)
print("%.6lf" % round(ans, 6))