けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

2016-01-01から1年間の記事一覧

AOJ 0115 Starship UAZ Advance

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

Codeforces Round #360 (Div. 1) A. NP-Hard Problem (R1500)

# 問題概要 無向グラフ (頂点数 n, 枝数 m) が与えられる。 このグラフの頂点集合を互いに disjoint な 2 つの集合 A, B に分割して、 A, B がともに vertex cover となっているようにせよ。 そのようなものが存在しなければ -1 をリターンせよ。 # 制約 2 ≤…