AOJ 1190 - つながれた風船
問題
提出コード
二度とやりたくないです。。。
今回は諸事情でC言語となっています。
自分は高校数学がとてもできないので、今回もさまざまなサイトにお世話になりました。
解法
ひたすら数学をします。
高さが最大になる可能性があるのは主に3パターンで、
1つの紐のみ張っているパターン
2つの紐が張っているパターン
3本以上張っているパターン
です。
どのパターンも、張っている紐をもとにして風船の座標を逆算し、その座標から残りの杭まで、紐の距離が足りているかどうかを調べ、足りているなら最大値を更新、足りていなければスルー、というようにしていけば答えを求めることができます。
ということで、上の3つのパターンについて、風船の座標を求めていきます。
1つの紐のみ張っているパターン
このパターンはすごく単純で、張っている紐の長さが高さそのものになり、xy座標も杭が刺さっている座標になります。2つの紐が張っているパターン
このパターンは、2つの杭を結ぶ線分が底辺で、2つの紐が残りの2辺である三角形が出来上がります。
底辺の長さは杭の距離なので求めることができ、三角形の面積も、3辺の長さがわかるため上記のサイトを参考にヘロンの公式を適用すれば求めることができるので、高さをここから求めることができます。
あとは、高さを求めることができれば、風船から地面に垂線をおろすことで直角三角形が2つでき、これにより、2つの杭を結ぶ線分が2つにわかれるので、その比をもとに風船のxy座標を求めることができます。3つ以上紐が張っているパターン
前提として、3つの杭が直線に並んでいる場合は、2つの紐のパターンで抑えられているため、計算途中で値が負になるなど、辻褄が合わなくなった時点で切り上げることにします。 4つ以上紐が張っているパターンは、3つ紐が張っているパターンに、たまたま＋αで張っている紐が存在していた、と考えれば良いです。なので、これが最後になります。
風船と3つの杭による四面体ができあがります。まずは先ほどと同様に高さを求めます。
これは、上記のサイトをまた参考にして、体積を求めた後、3つの杭による三角形の面積をヘロンの公式により求め、高さを割り出します。
そして一番の難関となるxy座標の求め方ですが、まず2つの杭を選びます。
そして、風船から地面に下した垂線の足と、その2つの杭がつくる三角形を利用して、座標を求めます。
この三角形は、長さをすべて求めることができて、
紐の長さ＋風船の高さ＋この三角形の長さ、からなる直角三角形2つから求める辺2本と、2つの杭の距離になっています。
ということで、2点の座標、3辺の長さが求まったということで、上記の記事を参考に、ゴリゴリ計算することで、xy座標を求めます。
この時、候補はまだ2つありますが、残った杭からの距離も辻褄があっていないといけないため、候補を1つに絞ることができます。
ということで、座標と高さが求まったので、これも残りの紐が条件を満たすかのチェックをしていけば良くなります。
とうだうだ書いてきましたが、コード量がとてつもない上に、適当にコーディングしていたら変数の数もとてつもない量になったので、頭がパンクしそうになりました。
終わってから調べてみると、三分探索等々もう少し賢い方法自体はあるみたいですね…
