题目详情题解（0）讨论（0）提交记录（0）

AT_kupc2018_l.凸包が映し出される平面

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

在三维空间中有 NN 个点，第 ii 个点的坐标为 (xi,yi,zi)(x_i, y_i, z_i)。

首先，你可以自由选择一个长度为 11 的三维向量 vv。

接下来，定义一个经过原点并垂直于向量 vv 的平面 FF。

对于每个点 (xi,yi,zi)(x_i, y_i, z_i)，作出这点到平面 FF 的垂线，垂足记为 pip_i。

在平面 FF 中，利用点 p1,p2,…,pNp_1, p_2, \ldots, p_N 构造出一个凸包，并计算它的面积 SS。

求出面积 SS 的最大值，并计算出能使 SS 达到最大值的向量 vv 的数量，最后将这个数量对 109+710^9 + 7 取模。

输入格式

输入由标准输入给出，格式如下：

$ N $ $ x_1 $ $ y_1 $ $ z_1 $ $ x_2 $ $ y_2 $ $ z_2 $ $ : $ $ x_N $ $ y_N $ $ z_N $

输出格式

输出面积 SS 的最大值，接着输出能使 SS 达到最大值的向量 vv 的数量对 109+710^9 + 7 取模的结果。

请注意，面积 SS 的最大值，如果绝对误差或相对误差小于 10−810^{-8}，则视为正确答案。

输入输出样例

  • 输入#1

    4
0 0 0
1 0 0
0 1 0
0 0 1

    输出#1

    0.866025403784
2

  • 输入#2

    4
0 0 0
0 1 1
1 0 1
1 1 0

    输出#2

    1.000000000000
6

  • 输入#3

    8
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

    输出#3

    1.732050807569
8

  • 输入#4

    27
0 0 0
0 0 1
0 0 2
0 1 0
0 1 1
0 1 2
0 2 0
0 2 1
0 2 2
1 0 0
1 0 1
1 0 2
1 1 0
1 1 1
1 1 2
1 2 0
1 2 1
1 2 2
2 0 0
2 0 1
2 0 2
2 1 0
2 1 1
2 1 2
2 2 0
2 2 1
2 2 2

    输出#4

    6.928203230276
8

  • 输入#5

    24
2 3 4
2 4 3
3 2 4
3 4 2
4 2 3
4 3 2
2 1 4
2 4 1
1 2 4
1 4 2
4 2 1
4 1 2
2 3 0
2 0 3
3 2 0
3 0 2
0 2 3
0 3 2
2 1 0
2 0 1
1 2 0
1 0 2
0 2 1
0 1 2

    输出#5

    14.282856857086
24

说明/提示

  • 输入的数值均为整数。
  • 4≤N≤604 \leq N \leq 60
  • 0≤xi,yi,zi≤1,0000 \leq x_i, y_i, z_i \leq 1,000
  • 每个点的坐标均不相同。
  • 所有点都不在同一个平面上。
  • 使得面积达到最大值的向量 vv 的选择方案数量有限。

样例解释 1

如果选择 v=(1/3, 1/3, 1/3)v = (1 / \sqrt{3},\ 1 / \sqrt{3},\ 1 / \sqrt{3})，则每个点到平面 FF 的垂足形成的凸包是一个边长为 2\sqrt{2} 的正三角形，其面积为 3/2\sqrt{3}/2，这正是面积的最大值。当选择 v=(−1/3, −1/3, −1/3)v = (-1 / \sqrt{3},\ -1 / \sqrt{3},\ -1 / \sqrt{3}) 时，也能得到同样的面积。因此，使凸包面积达到 3/2\sqrt{3}/2 的向量 vv 只有两个选择方案。

本翻译由 AI 自动生成

输入解题思路，AI测评打分。不知道怎么写?

首页