← 返回题目列表

AtCoder · scpc2026_div1_e

E. 我想成为棱镜

中文机器翻译题面 查看原题

表示言語

/ /

分数: 100 点

问题陈述

你被给予 N 三维空间中的点。该点的坐标 i第一点是 (x_i, y_i, z_i).

A sungjae0506 是一个三棱柱,其包含所有给定点在其边界上或内部,其底面垂直于 z-轴,并且其侧面垂直于 xy- 平面。

在所有可能的 sungjae0506 中,找到使得 \frac{\text{volume}}{\text{surface area}}.

约束

  • 3 \leq N \leq 100\,000
  • -10^8 \leq x_i, y_i, z_i \leq 10^8
  • 所有输入值均为整数。
  • 让 D 给定点中最远的一对之间的距离最小的 sungjae0506 的体积。 N 只给出了这样的情况:即使将每个给定点移动到距离其原始位置任意距离以内的位置, 10^{-6}D 最小化的 sungjae0506 \frac{\text{volume}}{\text{surface area}} 也是唯一存在的。

输入

输入由标准输入按以下格式给出:

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

输出

打印在所有可能的 sungjae0506 中最小化 \frac{\text{volume}}{\text{surface area}} 的 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개의 점 중 가장 거리가 먼 두 점 사이의 거리가 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