2次元平面上に障害物があるパスを見つける

Question

私は与えられたプログラミングタスクを解決しようとしていますが、それを行う方法は少ししかありません。

これは問題です：

スキニーピートは庭の誕生日パーティーに招待されます。彼はあまりにも多くのパーティーのような実際に をしていないが、誕生日のケーキは になるだろうと聞いて、彼はそれを試してみるチャンスを欠場したくないでしょう。

少し問題があります。園内にスプリンクラーシステム が設置されており、彼の友人を知ることで、誰かがパーティーのいたずらとしてそれをオンにする可能性が高くなります（ ）。ピートはケーキが好きだが、 は濡れているのが本当に嫌いだ。幸運にも彼は にスプリンクラーの場所があり、どのくらい遠くまで水を振りかけることができるかという庭のスケッチを見つけました。 水。

• 庭は、片側が開いて反対側に家がある矩形のように見えます。
• ケーキは家に入る予定です。
• 他の2辺にはフェンスがあり、そこから入ることができないため、家には入り口がありません。ピートは、 に興味があり、庭に入り、家に帰ることができるかどうかを知るためには、濡れてもよい。

簡潔にするため、庭の地図はデカルト座標座標系にあると考えることができます。

• ガーデンは、軸に平行な辺を持ち、左下隅が原点（0、0）にある矩形です。

• 庭への入り口は左側で、右側は家にあります。

• スプリンクラーは、中心と半径を持つ円として表されます。このようなサークルのどこかに足を踏み入れると、あなたは濡れるかもしれませ

• この問題の目的は、ピートがとても痩せているので、実際には 数字を座標として、彼を空間内を移動する単なる点と考えることができます。標準入力の

入力仕様最初の行は、2 スペースで区切られた整数HとW、高さと 庭の幅が含まれています。

次の行には、スプリンクラーの数Nが含まれています。そのあと、N行 には、Xi、Yi、Riの3つのスペースで区切られた整数が続きます。 センター（Xi、Yi）と の半径Riを持つ円としてのスプリンクラーの説明です。

1≤N 128

1≤H≤1024

0≤Xiの≤≤

0≤李≤W H W

1 Riを≤≤1024

出力仕様

出力「CAKEを含む単一の行

あなたは何のコードを示していないし、あなたが唯一の暗黙のうちに助けを求めるのでヘルパー

Answer 1

への事前のおかげで、私は重要なアイデアを与えるとあなたに数学と実装を残しておきます。

スキニーピートは、濡れないでケーキを得ることができます庭の底と上の間にスプリンクラーの鎖があります。言い換えれば、ピートが成功したと考えることができます。しかし、すべてのサークルを見てください。我々は、円が庭の下端と交差するかどうかを確認します。それは簡単な数学です。もし存在しなければ、ピートは本当に成功する。ある場合は、最初のものと交差する別の円があるかどうかを確認し、次に他のものが交差しているかどうかなどを確認します。最後に、この鎖の最後の円が庭の上端と交差するかどうかを確認します。庭の上下に交差する交差する円のような鎖がある場合、貧しいピートは空腹になります。 （上端と下端の両方に交差する1つの円だけがPeteを挫折させることになります）

コンテストPDFの2番目の例の図がありますPeteが成功するように、スパンニングサークルの連鎖はありません。

そして、ここでピートが失敗した第三の例の図です。左側には青色の4つの円の連なりがあり、庭にまたがっています。そのアイデアを考える

、庭の上側と下側と交差する円を見つけるために、交差円とO(N)アルゴリズムのすべてのペアを見つけるために明白なO(N^2)アルゴリズムがあります。あなたは、あなたの問題を解決するために、グラフ理論からの経路探索アルゴリズムを使用することができます。上下の辺とサークルをグラフのノードとして考えると、2つのノードが交差している場合はエッジで結ばれています。次に、上辺と下辺を表すノード間のパスを検索します。数学、アルゴリズム、およびコードを考え出す上

幸運。