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

ゆらのふなびと

競プロ, Python, C++

幾何

AOJ-ICPC 350 Railroad Conflict

メモ:直線の交点のパラメータの求め方について。 問題 黒い線分と赤い線分が合わせて n 本フィールドに散らばっている。フィールドには地上・地下の2つのレイヤーがあり、どの線分も地上または地下にある。今から青い線分を与えられた点A, B間に1本引く。青…

AOJ-ICPC 300 Building a Space Station

問題 n個の球がある。球iは中心(x_i, y_i, z_i), 半径r_iである。これらの球の間に必要であれば橋を架けることで、すべての球の間を連結にしたい。ただし最初から共有点を持つ球どうしや、片方がもう片方を内包するような球どうしは既に連結であるとみなす。…

SRM538 Div.1 Med(450) TurtleSpy

Div.1 Medium 初AC! 問題 TopCoder Statistics - Problem Statement ロボットに以下の命令を送ることができる。 その場で左(右)に向きをx度変える(xは1以上359以下の整数) 前(後ろ)に距離xだけ進む 使える命令文(「左に50度曲がる」など)が与えられるので…

ABC016 D - 一刀両断

他のブログを見て「なんで交差判定"2回"してるの??」と思った人用の記事。 問題 abc016.contest.atcoder.jp 多角形と、線分が与えられる。線分により、多角形はいくつの領域に分断されるか。 解法 公式の解答を見ると、(求める数) = (線分と交差する辺の数…

複素数をつかって三角形の外心を求める

「幾何の問題は複素数を使うと実装が軽くなるよ!」という噂を聞いたのでPythonでやってみた。 今回使うのはこちらの問題↓↓ Circumscribed Circle of a Triangle | Aizu Online Judge 三角形の頂点の座標が与えられるので、外接円の中心と半径を答えよという…