TopCoder Open 2019 挑战：将馅饼切成六块

在唤醒 “我们赢得了：TopCoder Open 2019” 我发布了算法轨道上的问题 （经典体育编程。在一个半小时内，您需要用 Java、C#、C++ 或 Python 解决三个问题。）

1. 六人份馅饼

制定问题

时间限制为 4 秒。

你有一个馅饼。 从上方观察时，蛋糕具有（严格）凸多边形的形状。 您将获得 X 和 Y 整数形式的顶点坐标。

你有五个朋友。 您想将饼图分成面积相等（但形状不一定相同）的六块。 当然，任何人都可以在五次剪辑中完成，但只有专业人士才能在三次剪辑中完成。

找到穿过一个点的三个直线切口，将馅饼分成六个相等的部分。 打印 {x, y, d1, d2, d3}，其中 (x, y) 是所有三个切口的公共点，d1, d2, d3 是切口的方向角（以弧度表示）。

定义类别：CakeForSix
方法：切割
参数：int[]、int[] 返回：double[] 方法签名：double[] cut(int[] x, int[] y)
（确保你的方法是公开的）

笔记

• 沿 x 轴的正方向为 0（弧度），沿 y 轴的正方向为 pi/2（弧度）。
• 对于任何整数 k，d 方向上的切割类似于 pi*k+d 方向上的切割。
• 您可以输出任何方向，它们不必来自 [0, pi)。
• 分级员会双倍计算你的六块蛋糕的面积。 如果它们之间的相对或绝对差异小于 10^(-4)，则答案将被接受。
• 更准确地说，让 X 和 Y 为分级员计算出的六个区域中最小和最大的一个。 如果是，那么您的答案将被接受
• （问题的原始版本使用的精度为 1e-7 而不是 1e-4。为了解决存档中的此问题，由于存在调用案例，精度限制被降低，这可能会使问题无法以精度解决1e-7。在理想世界中，极限不允许出现这种情况，并且仍然需要高精度，因此用一些通用的数值优化来解决问题并不容易。）

限制

• x 包含 3 到 50 个元素（含）。
• y 包含与 x 相同数量的元素。
• 0 到 10 之间的所有坐标（含 000 和 XNUMX）
• x 和 y 定义逆时针方向的凸多边形。

原文为英文

问题陈述

时间限制为 4 秒。

你有一个蛋糕。 从上面看，蛋糕是一个（严格的）凸多边形。 int[]sx 和 y 中给出了其顶点的坐标。

你有五个朋友。 您现在想要将蛋糕切成面积相等（但形状不一定相等）的六块。 当然，任何人都可以在五次切割中做到这一点 - 但只有真正的专业人士才能在三次切割中做到这一点！

找到穿过同一点的三个直线切口，将蛋糕切成六个同样大的部分。 返回 {x, y, d1, d2, d3}，其中 (x, y) 是三个切口的公共点，d1, d2, d3 是它们的弧度方向。

定义

类别：CakeForSix
方法：切割
参数：int[]、int[] 返回：double[] 方法签名：double[] cut(int[] x, int[] y)
（确保你的方法是公开的）

— x 轴正方向为 0（弧度），y 轴正方向为 pi/2（弧度）。
— 对于任何整数 k，沿 d 方向的切割与沿 pi*k+d 方向的切割相同。
— 您可以返回任何方向，它们不必来自 [0,pi)。
— 分级员将双倍计算六块蛋糕的面积。 如果它们之间的相对或绝对差异小于 10^(-4)，则答案将被接受。
— 更准确地说，让 X 和 Y 分别为评分者计算出的六个区域中最小和最大的区域。 然后，如果 Y < max( X + 10^(-4), X * (1+10^(-4)) )，您的答案将被接受。
—（问题的原始版本使用 1e-7 精度而不是 1e-4。为了解决存档中的此问题，由于存在挑战案例，精度限制被降低，这些挑战案例很可能导致任务无法以 1e-7 精度解决在理想的世界中，约束不允许出现这种情况，并且仍然需要高精度，因此通过一些通用的数值优化来解决问题并不容易。）

限制
— x 将包含 3 到 50 个元素（含）。
— y 将具有与 x 相同数量的元素。
— 所有坐标都在 0 到 10,000 之间（含）。
— x 和 y 将按逆时针顺序描述凸多边形。

Примеры

0)

{0，20，30，50，30，20}
{10，0，0，10，20，20}
返回：
{24.999999999437453、9.999999999500002、0.0、0.7266423406817211、2.4149503129080787}

对称但不规则的六边形。 示例答案相当于将其水平切成两半，然后沿着中心进行另外两次切割，将每块分成三块。

1)

{0，1000，0}
{0，0，1000}
返回：
{333.3333333331763、333.3333333332546、0.7853981633986264、2.0344439357948154、2.6779450445891753}

直角三角形。 同样，我们可以从沿对称轴的三个切口之一开始。

2)

{40，70，90，90，50}
{30，20，40，100，60}
返回：
{69.79517771922892、52.77575974637605、2.0616329654335885、3.637826104091601、4.32123485812475}

不规则五边形。

3)

{300，400，300，200}
{500，600，700，600}
返回：{299.99999999974995、599.9999999995、0.0、1.107148717794088、2.034443935795705}

一个正方形旋转了45度。

[源]

只有注册用户才能参与调查。 登录拜托

我解决了这个问题

• 不到 10 分钟

• 10 30分钟

• 30 60分钟

• 1 2小时

• 2个多小时内

• 其他

42 位用户投票。 47 名用户弃权。

来源： habr.com