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

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Codeforces Round #340 (Div. 2) D. Polyline

Hack だらけで嫌になる問題。

codeforces.com

問題概要

二次元平面上の 3 点が与えられる。3 点すべてを通過する軸に平行な polyline を描く。 このような polyline を描くのに最小で何本の線分が必要だろうか。

解法

・1 本で構成できる場合
x 座標がすべて等しいか y 座標がすべて等しいとき。

・2 本で構成できる場合
y 座標が等しい点の対があって、残りの点が緑色の領域にあるとき。

f:id:pekempey:20160124155058p:plain

x 座標が等しい場合も同様。

・3 本で構成できる場合
上記のケースに該当しないとき。


同じような場合分けを何度も書かないように next_permutation した。

Codeforces Round #340 (Div. 2) D. Polyline

簡単だけど微妙にバグる