SRM368

Rate1632->1746

250

何も考えずにBFSしてこける．何を間違えたかというと

●→●→●
    ↓　↓
　　●←●

上のような時にループがあると判定してた．そして去年の模擬国内予選のCでも似たようなことして間違えてたことを思い出した．

500

polylineどうしの接続関係をだしたら，あとはDFSなりBFSで解ける．
polylineどうしが交わっているかどうかの判定は基本的にはそれぞれの線分対にたいして交差判定をすればいい．ただ一点の場合とかで場合分けする必要がある．