E: Connected? - AtCoder Regular Contest 076
RxC の平面内に (x1[i], y1[i]) (x2[i], y2[i]) の座標のペアが幾つか与えられる。このペア同士で線を引きたいが、それぞれの線が交差してはならない。そのような引き方が可能かどうか判定せよ。
まず、両方の点のいずれかが周囲を除いた領域RxCの内部にある時、そのペアは無視してもよい。なので、両方の点が領域の周辺にあるものだけを考える。
これはある角から出発して辺を一周するような順序で点をソートし、順番にキューに入れていく。既にキューに入れたものが現れた場合、キューの先頭にもう片方のペアがあるならばキューから出す。そうでない場合は線が引けないのでNOを出力する。これを最後までやればよい。ソートが一番重く、O(N logN)。
