その結果、 アルゴリズムトラックから問題を公開します (古典的なスポーツ プログラミング。XNUMX 時間半で、Java、C#、C++、または Python で XNUMX つの問題を解く必要があります。)
1. XNUMX人分のパイ
問題の定式化
制限時間は4秒です。
パイがあるよ。 上から見ると、ケーキは（厳密には）凸多角形の形をしています。 頂点の座標は X および Y の整数で与えられます。
あなたにはXNUMX人の友達がいます。 パイを等しい面積の XNUMX つの部分に分割したいとします (ただし、必ずしも同じ形である必要はありません)。 もちろんXNUMXカットなら誰でもできますが、XNUMXカットでできるのはプロだけです。
パイを 1 等分する 2 点を通る直線で 3 つの切り込みを見つけます。 {x, y, d1, d2, d3} を出力します。ここで (x, y) は XNUMX つのカットすべての共通点、dXNUMX、dXNUMX、dXNUMX はカットの方向角 (ラジアン単位) です。
定義クラス: ケーキフォーシックス
方法:カット
パラメータ: int[]、int[] 戻り値: double[] メソッド シグネチャ: double[] Cut(int[] x, int[] y)
(メソッドがパブリックであることを確認してください)
注釈
- x 軸に沿った正の方向は 0 (ラジアン)、y 軸に沿った正の方向は pi/2 (ラジアン) です。
- d 方向のカットは、任意の整数 k の pi*k+d 方向のカットと同様です。
- 任意の方向を出力できますが、[0, pi) からである必要はありません。
- 採点者は、10 個のケーキの面積を 4 倍で計算します。 それらの間の相対的または絶対的な差が XNUMX^(-XNUMX) 未満の場合、答えは受け入れられます。
- より正確には、採点者が計算した 10 つの領域の最小値と最大値を X と Y とします。 Y の場合、あなたの回答は受け入れられます。
- (問題の元のバージョンでは、1e-7 ではなく 1e-4 の精度が使用されていました。アーカイブでこの問題を解決するために、精度の制限は、問題を精度で解決できなくなる可能性がある呼び出しケースの存在により引き下げられました。理想的な世界では、このようなケースは制限によって許可されておらず、依然として高精度が必要であるため、一般的な数値最適化で問題を解決するのは簡単ではありません。)
制限
- x には 3 ～ 50 個の要素が含まれます。
- y には x と同じ数の要素が含まれます。
- 0 から 10 までのすべての座標
- x と y は反時計回りの凸多角形を定義します。
英語の原文
問題提起
制限時間は4秒。
ケーキがありますね。 上から見ると、ケーキは（厳密には）凸多角形です。 その頂点の座標は int[]sx と y で与えられます。
あなたにはXNUMX人の友達がいます。 ここで、ケーキを同じ面積の XNUMX つの部分に切りたいとします (ただし、必ずしも同じ形である必要はありません)。 もちろん、誰でも XNUMX カットでそれを行うことができますが、XNUMX カットでそれを行うことができるのは真のプロだけです。
ケーキを同じ大きさの 1 つの部分に切り分ける、同じ点を通る 2 つの直線の切り込みを見つけます。 {x, y, d3, d1, d2} を返します。(x, y) は 3 つのカットの共通点、dXNUMX、dXNUMX、dXNUMX はラジアン単位の方向です。
定義
クラス: ケーキフォーシックス
方法:カット
パラメータ: int[]、int[] 戻り値: double[] メソッド シグネチャ: double[] Cut(int[] x, int[] y)
(メソッドがパブリックであることを確認してください)
ノート
— x 軸に沿った正の方向は 0 (ラジアン)、y 軸に沿った正の方向は pi/2 (ラジアン) です。
— d 方向のカットは、任意の整数 k の pi*k+d 方向のカットと同じです。
— 任意の方向を返すことができますが、[0,pi) からである必要はありません。
— 採点者は、ケーキ 10 個の面積を 4 倍で計算します。 それらの間の相対的または絶対的な差が XNUMX^(-XNUMX) 未満の場合、答えは受け入れられます。
— より正確には、採点者が計算した 10 つの領域の最小値と最大値を X と Y とします。 次に、 Y < max( X + 4^(-1), X * (10+4^(-XNUMX)) ) の場合、答えは受け入れられます。
— (問題の元のバージョンでは、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 }
対称的だが不規則な六角形。 解答例は、水平に半分に切り、中央にさらに XNUMX つの切り込みを入れて、各部分を XNUMX つの部分に分割することに対応しています。
1)
{0、1000、0}
{0、0、1000}
戻り値：
{333.3333333331763、333.3333333332546、0.7853981633986264、2.0344439357948154、2.6779450445891753 }
直角三角形。 繰り返しますが、対称軸に沿った XNUMX つのカットのうちの XNUMX つから始めることができます。
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