No.245

ある直線を考え, 任意の1点を固定して回転させ, 貫く線分の数が変わるところを見ると, それはどれかの線分の端点である.

今度はその端点で固定して同様に回転させ, 貫く線分の数が変わるところを見ると, それもまたどれかの線分の端点である.

したがって, すべての2端点を結ぶ直線で貫く本数を全探索し, 貫く線分の本数を求めればいい.

点 $A, B$ を結ぶ直線と $C, D$ を結ぶ線分が交点を持つかどうかは, ベクトルの外積(の $z$ 成分)を使って,

$$(\overrightarrow{AB} \times \overrightarrow{AC})(\overrightarrow{AB} \times \overrightarrow{AD}) \leq 0$$

で判定できる.