Area1 https://blog.hatena.ne.jp/Area1/ Area1のif(memo[i][j]) https://area.hateblo.jp/ SRM 文字列処理 幾何 問題 折れ線グラフが以下の形式で1つ以上与えられる。互いに交差している折れ線グラフを1つの集合と数えると、いくつの集合になるか。1つの折れ線は1つ以上の線分からなり、点同士は'-'で区切られ、点は','で区切られる2つの非負整数で表現される。' 'で区切られているものは別の折れ線に属する。 やりかた 与えられる書式を処理しやすいように整形するのが面倒。折れ線グラフもすべて1つの線分に分解してしまったのち、各線分同士の交差をすべて調べてUnion-Findしていくつのグループになるか調べるのが手っ取り早い。以下きたないソース。 //Union-Findのソースは略 struct seg{ int… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Farea.hateblo.jp%2Fentry%2F2015%2F11%2F23%2F235109" title="SRM 368 Div1 Medium PolylineUnion - Area1のif(memo[i][j])" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2015-11-23 23:51:09 rich https://area.hateblo.jp/entry/2015/11/23/235109 1.0 100%