PCK2022 Final - 12

一体誰がこんな問題を！？

問題

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Final/4011

雑な問題概要

三角形がたくさん与えられます、マージしてください。

三角形同士が重なったり、最終的に穴ができたり、その他へんなケースはありません。

解法

三角形を「向き付けされた3つの線分の集合」と考え、逆方向の線分があるときはそのぶんだけ相殺されるようにしながら集合をマージしていけばよいです。

線分が乗っている直線の特定、各直線上でのイベントソート+imos、残った線分の列挙、線分をマージして多角形を構成のようにして解きますが、それらはすべて整数で行えるため、この問題は誤差なしで解くことができます。

類題

多角形の集合 A, B が与えられます。同一集合内の多角形は面積を共有しません。

同様にしてマージしていったときにできる多角形の集合が、A と B で同じものになるか判定してください。

類題の解法

A, B での線分の向き付けをそれぞれ右手系/左手系で考えてマージし、すべてが相殺されたら同じものです。