AOJ 2003 - Railroad Conflict

問題
提出コード

解法

経路は線分で、入力が与えられた時点で全て決まっているため、選ぶことができるのはどの箇所を地上に、どの箇所を地下にするか、です。
新しくつくる路線が既存の路線と交差する地点もはじめから決まっているので、それらはあらかじめ計算することで求めることができます。
すると、その交差する地点それぞれでは、地上にするべきか地下にするべきかがわかります。
新しく作成する路線の線分上にその交点を並べたとき、ある点とその隣の点で地上にあるべきか地下にあるべきか、が異なる箇所がありますが、その部分では出入口を作らなければなりません。逆に、そのほかの箇所で出入口をつくる必要はありません。
よって、新しくつくる路線と既存の路線の交点を調べ、それを並べて端から見ていき、地上と地下が入れ替わる箇所の個数が答えになります。