3 次元幾何の練習 問題へのリンク 問題概要 円錐を平面によって切断するとき、分離された2つの部分の体積を求めよ。 解法 ちょっと複雑だが、2次元に射影して考える。 そのためには、3次元幾何の正射影が必要になる #include <iostream> #include <vector> #include <cmath> #include <iomanip></iomanip></cmath></vector></iostream>…

えーーーーー、どうしてバグに気づかなかった。。。orz 問題へのリンク 問題概要 x 軸上に斜辺を持つような直角二等辺三角形 (三頂点はどれも格子点) が N 個与えられる。N 個の直角二等辺三角形によって被覆される格子点の総数を求めよ。 制約 1 <= N <= 10…

これ面白い！！！！！！！！ 好き！！！！！！！ 問題へのリンク 問題概要 平面上に 個の点の座標 と、それらを結ぶ 本の線分がある。 線分のある部分は通過ができないので、線分に囲われた領域とその外側の領域とは行き来することができない。 そこでいくつ…

の Kruskal 法ではダメで、 な Prim 法なら OK という稀有なパターンの問題。Dijkstra 法でも priority_queue を使ったやつは 愚直なやつは と二種類の実装があって前者の方が速いと言及されるケースも多いけど、密グラフ ( なグラフ) では後者の方が速い。P…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0115 三次元幾何 問題概要 三次元空間上で、線分 s と三角形領域 t が与えられる。 s と t とが交点をもつかどうか判定せよ。 解法 まず、sを延長した直線と、tを延長した平面との交点 p を求める…

最近、ABC 201〜300 の D 問題埋めを推奨している身としては、僕も同様のトレーニングとして SRM 401〜650 辺りの DIV1 Hard 埋めを始めてみようと思い立った。 問題へのリンク editorial へのリンク 問題概要 二次元平面上において、以下の条件を満たす線分…