Hello Barcelona Day4

Day3はLink-Cut木コンテストだったんですが、むずすぎたのでもうちょっと理解してから記事にしようと思います。 Day4はstereometry(空間の幾何?)コンテスト

A - Elementary

問題

4点与えられるのでそれらを頂点とする四面体の体積を求めて、という問題

解法

三重積を計算して6で割るだけ

B - Cross Spider

問題

 1 \le n \le 100000点が与えられるので同一平面上にあるか判定せよ。XYZ座標はそれぞれ絶対値が1000000以下。

解法

座標が大きく、内積外積の演算をするとdoubleでは誤差が心配(ギリギリいけそうだけど)なのでlong longで計算する。 平面の法線ベクトルが確定したらあとはそれと直交するかをみればいいだけ。

C - Line Teleportation

@kenshinが知らない間に通してた。

D - Segment Distance in 3D

この前まとめました。

xuzijian629.hatenablog.com

E - 3D Printing

問題

30面程度の凸な多面体が与えられるので体積を求めよ、という問題

解法

@oginginが通してくれた。

H - Connected Rings

リングが2つ与えられるので、鎖状につながっているか判定せよ。リング同士が交点をもつことはない。

解法

@kenshinが気合で座標計算し、通してくれた。プロすぎる。

感想

この日は自明問題しか貢献できなくて厳しい気持ちになった。