AT_scpc2026_div1_e.I Wanna be The Prism

You are given $N$ points in three-dimensional space. The coordinates of the $i$-th point are $(x_i, y_i, z_i)$.

A sungjae0506 is a triangular prism that contains all the given points on its boundary or in its interior, has bases perpendicular to the $z$-axis, and has lateral faces perpendicular to the $xy$-plane.

Among all possible sungjae0506s, find the volume of the sungjae0506 that minimizes $\frac{\text{volume}}{\text{surface area}}$.

给你三维空间中的 $N$ 个点。第 $i$ 个点的坐标为 $(x_i, y_i, z_i)$。

一个 sungjae0506 是一个三棱柱，满足以下条件：

• 包含所有给定点（在边界上或内部）；
• 两个底面垂直于 $z$-轴；
• 三个侧面垂直于 $xy$-平面。

在所有可能的 sungjae0506 中，求使比值 $\frac{\text{体积}}{\text{表面积}}$ 最小的那个 sungjae0506 的体积。

The input is given from Standard Input in the following format:

$N$
$x_1$ $y_1$ $z_1$
$x_2$ $y_2$ $z_2$
$\vdots$
$x_N$ $y_N$ $z_N$

输入从标准输入中按以下格式给出：

$N$
$x_1$ $y_1$ $z_1$
$x_2$ $y_2$ $z_2$
$\vdots$
$x_N$ $y_N$ $z_N$

Print the volume of the sungjae0506 that minimizes $\frac{\text{volume}}{\text{surface area}}$ among all possible sungjae0506s. An absolute or relative error of at most $10^{-9}$ is accepted.

输出使 $\frac{\text{体积}}{\text{表面积}}$ 最小的所有 sungjae0506 中的体积。允许的绝对或相对误差不超过 $10^{-9}$。

表示言語

/ /

Constraints

• $3 \leq N \leq 100\,000$
• $-10^8 \leq x_i, y_i, z_i \leq 10^8$
• All input values are integers.
• Let $D$ be the distance between the farthest pair among the given $N$ points. Only cases are given in which, even if each given point is moved to an arbitrary position within distance $10^{-6}D$ from its original position, the sungjae0506 minimizing $\frac{\text{volume}}{\text{surface area}}$ exists uniquely.

表示语言

/ /

约束条件

• $3 \leq N \leq 100\,000$
• $-10^8 \leq x_i, y_i, z_i \leq 10^8$
• 所有输入值均为整数。
• 设 $D$ 为给定的 $N$ 个点中距离最远的一对点之间的距离。仅考虑如下情形：即使将每个给定点在其原始位置周围半径为 $10^{-6}D$ 的范围内任意移动，使得 $\frac{\text{体积}}{\text{表面积}}$ 最小化的 sungjae0506 仍唯一存在。