読者です 読者をやめる 読者になる 読者になる

h_nosonの日記

競プロなど

幾何

Codeforces Round #365 (Div. 2) C. Chris and Road

問題 Problem - C - Codeforces N角形のバスがやってくる.幅Wの道路をバスにぶつからずに渡るとき,最短の渡る時間を求める問題 解法 バスを固定すると人が右上に向かって移動することと等しくなる.もしぶつからずにそのまま行けるのであればそのまま行く…

yukicoder No.132 点と平面との距離

問題 No.132 点と平面との距離 - yukicoder 3次元上の点と個の点が与えられる. をから点を通る平面への距離とした時, を求める問題.解法 ベクトル,ベクトル,ベクトルに囲まれた三角錐の体積を求め,三角形の面積で割って3をかけることで,高さつまり…

yukicoder No.199 星を描こう

問題 No.199 星を描こう - yukicoder XY座標上の点が5つ与えられる.点を線で繋いで星が描けるかどうかを判定する.解法1 それぞれの頂点を結ぶ線分をすべて考えて, 他の線分と交わる回数が2回のものが5つあれば星を描ける(端は数えません). 交点の求…

POJ 2932 Coneology

問題 2932 -- Coneology 平面上に円がN個あり,それらが交わることはない. どの円にも囲まれていない円はいくつあるか.解法 x座標の小さい方から走査していく. 走査する直線が円の左端にぶつかった時,その円が他の円に含まれているか調べる. この時,調…