Intersection

http://acm.pku.edu.cn/judgeonline/problem?id=1401
線分と長方形の交わり(Intersection)を判定する。
線分や長方形を点の集合とみなしたとき、intersectionが非空かどうか。

基本的には、
線分と線分の交わりを判定するサブルーチンを作り、
長方形の四辺いずれかと線分との交わりを判定させる。

線分と線分の交わりは、一方の線分を延長して直線にし、
他方の線分と交わるかを調べ、逆も成り立つかを調べることで行う。
具体的には、一方の線分の傾きと切片を求め、
その片側だけに他方の両端点が来る場合は交わらない、と判定する。
（事実上交点を求めている）

例外：
長方形の中に線分が含まれる場合は、四辺との交わりがなくても、交わっている
片方の線分が垂直な場合は、傾きがとれないので特別扱い
片方の線分が点の場合は、やはり特別扱い

手法が泥臭すぎるのは仕様。
せめて、線分の交わりの判定は何とかならないものか。

Java はメモリ食いすぎ、時間も遅すぎ。
小さい問題だとオーバーヘッドが強く影響する。

岡本先生のプログラムは、だいたい同じ考えで作られている。
違いは、「長方形の中に線分」の扱いと、線分同士の交わり。
「中」よりも緩い条件である「長方形の中に線分の端点のいずれか」がいえれば、
交わっていることが分かる。
（線分の両端点が中、を言わなくてもいい）
線分同士の交わりは、片方が垂直な場合について細かい場合わけにより判定。
片方が水平な場合、XYを反転して↑に渡す。