この問題は、スイスチーズモデル (Hard) とは、タイトルの Easy/Hard の表記および赤字の部分のみが異なります。 ただし、Hard と Easy では解法が異なります。Hard の解法で Easy も解けるわけではないことに注意してください。
リスク分析のモデルのひとつに、スイスチーズモデルというものがあります。 安全対策が何層もあっても、それぞれの対策には弱点があります。その弱点が偶然つながると、事故がすべての層を通り抜けてしまう、という考え方です。
あなたは、このモデルを何枚かのチーズを使って単純化し、分析することにしました。 各チーズは厚さが の平らな板で、 軸方向と 軸方向に無限に広がっているものとします。 チーズには手前から順に から までの番号が付いています。チーズ の前面は平面 上に、後面は平面 上にあります。 したがって、すべてのチーズの前面と後面は 平面に平行で、隣り合うチーズは隙間なく面を接しています。
行目に、チーズの枚数 が与えられる。
続いて、チーズ からチーズ までの情報が順に与えられる。各チーズの情報の最初の行には、そのチーズに開いている穴の個数 が与えられる。続く 行には、整数 , , が空白区切りで与えられる。これは、 平面に平行な断面が中心 、半径 の円板となる穴を表す。
事故がすべてのチーズを通り抜けられない、すなわち配置が安全ならば YES を出力せよ。そうでなければ NO を出力せよ。
入力例 では、平面上の点 が 枚すべてのチーズの穴の断面に含まれます。そのため、 から まで 軸に平行に移動すればすべてのチーズを通り抜けられ、答えは です。
各チーズには、前面から後面まで貫通する円柱状の穴が 個以上開いています。すべての穴の軸は 軸に平行です。 そのため、穴を 平面に平行な平面で切った断面は、どの深さでも中心の座標 と半径が同じ円板です。ここで、円板とは円周とその内部を合わせた領域を指します。すべてのチーズで共通の座標系を用います。
事故を、大きさのない点が移動するものとして表します。移動中は常に、いずれかのチーズの穴の内部または穴の境界上にいなければなりません。
事故は穴の中で自由に向きを変えて移動できます。同じチーズにある つの穴の断面が 点でも共有していれば、それらの穴の間を移動できます。また、隣り合う 枚のチーズが接する面で穴の断面が 点でも共有していれば、それらのチーズの間を移動できます。このとき、手前のチーズへ戻ることもできます。
最初のチーズの前面にあるいずれかの穴から出発して、最後のチーズの後面にあるいずれかの穴まで移動できるならば、このチーズの配置は安全ではありません。
与えられたチーズの配置について、事故が最後まで通り抜けられず、安全であるかを判定してください。
NO入力例 では、 つの穴の断面が平面上の点 で接しています。穴の境界上を通ることもできるので、 から まで移動できます。したがって、答えは NO です。
入力例 では、チーズ の中で複数の穴を順に通り、右へ移動することができます。そのため、チーズ とチーズ の穴が直接つながっていなくても事故は最後まで進むことができ、答えは NO です。