Hello Barcelona Day4
Day3はLink-Cut木コンテストだったんですが、むずすぎたのでもうちょっと理解してから記事にしようと思います。 Day4はstereometry(空間の幾何?)コンテスト
A - Elementary
問題
4点与えられるのでそれらを頂点とする四面体の体積を求めて、という問題
解法
三重積を計算して6で割るだけ
B - Cross Spider
問題
点が与えられるので同一平面上にあるか判定せよ。XYZ座標はそれぞれ絶対値が1000000以下。
解法
座標が大きく、内積や外積の演算をするとdoubleでは誤差が心配(ギリギリいけそうだけど)なのでlong longで計算する。 平面の法線ベクトルが確定したらあとはそれと直交するかをみればいいだけ。
C - Line Teleportation
@kenshinが知らない間に通してた。
D - Segment Distance in 3D
この前まとめました。
E - 3D Printing
問題
30面程度の凸な多面体が与えられるので体積を求めよ、という問題
解法
@oginginが通してくれた。
H - Connected Rings
リングが2つ与えられるので、鎖状につながっているか判定せよ。リング同士が交点をもつことはない。
解法
@kenshinが気合で座標計算し、通してくれた。プロすぎる。
感想
この日は自明問題しか貢献できなくて厳しい気持ちになった。