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}} $ .

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 $

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.

### 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.