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 和 XNUMX 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 名用戶棄權。

來源： www.habr.com