/ 
Time Limit: 1 sec / Memory Limit: 1024 MiB
表示言語
/ /Score : 100 points
Problem Statement
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}}.
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.
Input
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
Output
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.
Sample Input 1
6 88 848 44 -159 810 8 45 522 -21 163 793 -27 -143 706 -106 201 546 -71
Sample Output 1
15570000.000000000000000
表示言語
/ /Score : 100 points
문제
3차원 공간의 점 N개가 주어진다. 그중 i번째 점의 좌표는 (x_i, y_i, z_i)이다.
sungjae0506은 주어진 모든 점을 경계 및 내부에 포함하고 밑면이 z축에 수직이고 옆면이 xy평면에 수직인 삼각기둥이다.
가능한 sungjae0506 중 \frac{\text{부피}}{\text{겉넓이}}가 최소인 sungjae0506의 부피를 구해 보자.
제한
- 3 \leq N \leq 100\,000
- -10^8 \leq x_i, y_i, z_i \leq 10^8
- 입력으로 주어지는 수는 모두 정수이다.
- 주어진 N개의 점 중 가장 거리가 먼 두 점 사이의 거리가 D라 할 때, 주어진 점들을 원래의 위치로부터 10^{-6}D 이하만큼 떨어진 임의의 위치로 이동시켜도 \frac{\text{부피}}{\text{겉넓이}}가 최소인 sungjae0506이 유일하게 존재하는 경우만 주어진다.
입력
입력은 다음 형식으로 표준 입력으로 주어진다.
N x_1 y_1 z_1 x_2 y_2 z_2 \vdots x_N y_N z_N
출력
가능한 sungjae0506 중 \frac{\text{부피}}{\text{겉넓이}}가 최소인 sungjae0506의 부피를 출력한다. 절대/상대 오차는 10^{-9}까지 허용한다.
입력 예 1
6 88 848 44 -159 810 8 45 522 -21 163 793 -27 -143 706 -106 201 546 -71
출력 예 1
15570000.000000000000000
表示言語
/ /配点 : 100 点
問題文
3 次元空間上の N 個の点が与えられます．そのうち i 番目の点の座標は (x_i, y_i, z_i) です．
sungjae0506 とは，与えられたすべての点を境界および内部に含み，底面が z 軸に垂直で，側面が xy 平面に垂直な三角柱です．
可能な sungjae0506 のうち，\frac{\text{体積}}{\text{表面積}} が最小となる sungjae0506 の体積を求めてください．
制約
- 3 \leq N \leq 100\,000
- -10^8 \leq x_i, y_i, z_i \leq 10^8
- 入力はすべて整数
- 与えられた N 個の点のうち，最も距離が遠い 2 点間の距離を D とします．与えられた各点を元の位置から距離 10^{-6}D 以下の任意の位置に移動させても，\frac{\text{体積}}{\text{表面積}} が最小となる sungjae0506 が一意に存在する場合のみが与えられます．
入力
入力は以下の形式で標準入力から与えられる．
N x_1 y_1 z_1 x_2 y_2 z_2 \vdots x_N y_N z_N
出力
可能な sungjae0506 のうち，\frac{\text{体積}}{\text{表面積}} が最小となる sungjae0506 の体積を出力せよ．絶対誤差または相対誤差が 10^{-9} 以下であれば正解とみなされる．
入力例 1
6 88 848 44 -159 810 8 45 522 -21 163 793 -27 -143 706 -106 201 546 -71
出力例 1
15570000.000000000000000