実践練習のまとめ?

Problem C (1075) A thread in a space †

概要 †

• 三次元上での計算が必要な図形問題.
• 比較的容易な問題ではあるが, 図形特有のハマリに陥らないようにしないといけない.

内容 †

• 三次元空間上に球があり, その外に2つの点がある.
• 2つの点を糸で結んだ時に, その最短の長さを求める.
  • ただし, 糸は球の内部を通ることはできない.

解法 †

2点間の距離のような簡単なものの他, 次のような計算が必要

• 三次元空間における直線と点の距離
  • 二次元であれば有名な公式がある.
  • 三次元では, ベクトルの内積を使って式をたてると簡単か.
• 球に対する接線, 接点までの距離
  • ベクトルで考えれば, 二次元における接線と同じ
• 三次元の球上の2点間の角度
  • 2点を結ぶ弦と中心との距離を使って求めれば, 二次元の場合と同じ.

これらを組み合わせれば, ほぼできあがり.

議論 †

図形問題でしたが, 皆さんの出来は？？？

• 最短の長さを与える図形は簡単に思いつく.
  • 特にSample Inputが良心的
• 例外に対する処理をきちんとやらないといけない.
  • 0除算の判定, √内の正の判定
  • 線分A, Bが球と交わらない
    • 直線までの距離が遠い
    • 直線上で中心に最も近い点が, 線分の外
    • A, Bが同一点だと？

プログラム †

• 松崎
  1075.matsuzaki.cpp