DouKaku?

package jp.yukoba.ioi2007;

import scala.collection.mutable._

object Flood4 extends Application {
  class Base
  case class Point(x:int, y:int) extends Base {
    def < (that:Point) = (y < that.y || (y == that.y && x < that.x))
  }
  case class Wall(no:int, from:Point, to:Point) extends Base {
    def < (that:Wall) = (from < that.from)
  }
  
  // 点番号 -> Point
  val N = readInt
  val dotMap = Map(List.tabulate(N, i => {
    val line = readLine.split(" ").map(Integer.parseInt(_))
    (i+1, Point(line(0), line(1)))
  }):_*)
  // 壁番号 -> Wall
  val W = readInt
  val wallMap = Map(List.tabulate(W, i => {
    val ary = readLine.split(" ").map(Integer.parseInt(_))
    // 左上に近いのを from に設定
    val p1 = dotMap(ary(0))
    val p2 = dotMap(ary(1))
    if(p1 < p2)
      (i+1, Wall(i+1, p1, p2))
    else
      (i+1, Wall(i+1, p2, p1))
  }):_*)
  // 訪れていない壁番号のセット
  val unvisited:Set[int] = Set(wallMap.keys.toList:_*)
  // ソート済みの壁の壁番号の配列
  val sortAry = wallMap.keySet.toList.sort((n1, n2) => 
      wallMap(n1) < wallMap(n2)).toArray
  // 上のたどっていくポインタ
  var sortAryPos = 0
  // {たどった壁} {両方水の壁}
  val visited = Set[int]()
  val bothWater = Set[int]()
  val brokenWall = Set[int]()
  // Point -> Wallの配列
  val point2wallAry = Map[Point, Array[(Wall,int)]]()
  for(pointNo <- dotMap.keys) {
    // 頂点から出る壁は１～４つ
    val point = dotMap(pointNo)
    point2wallAry(point) = new Array[(Wall,int)](4)
  }
  for(wallNo <- unvisited) {
    def put(p:Point, wallDir:(Wall,int)) {
      val ary = point2wallAry(p)
      for(i <- 0 until (ary.length)) {
        if(ary(i) == null) {
          ary(i) = wallDir
          return
        }
      }
      error("ここにはこない")
    }
    val wall = wallMap(wallNo)
    put(wall.from, (wall, 1))
    put(wall.to, (wall, -1))
  }
  
  while(unvisited.size > 0) {
    //println(unvisited)
    // [全ての壁|座標でソート済み]in{まだたどっていない壁}から最初の壁をとる。次はこの配列番号から。
    def getFromSortAry():int = {
        while(true) {
          val wallNo = sortAry(sortAryPos)
        if(unvisited.contains(wallNo)) return wallNo
        sortAryPos += 1
        }
      error("ここにはこない")
    }
    var wallNo = getFromSortAry
    var wall = wallMap(wallNo) 
    // 左手に水:int＝頂点から右方向に壁 なら 1 下方向なら -1
    val isLeftWater = if(wall.from.y == wall.to.y) 1 else -1
    //println("isLeftWater = " + isLeftWater)
    // 壁のたどる方向、1 = from -> to、-1 = to -> from
    var wallDir = 1
    // 最初の壁に戻ってくるまで、壁をたどる (do-while)
    val firstWallNo = wallNo
    val firstWallDir = wallDir
    def loop() {
      while(true) {
        //println("wall = " + wall + ", wallDir = " + wallDir)
        //{たどった壁}に入っている => {たどった壁}から{両方水の壁}へ移動
        //  else {まだたどっていない壁}から{たどった壁}へ移動
        if(visited.contains(wallNo)) {
          visited -= wallNo
          bothWater += wallNo
        } else {
          unvisited -= wallNo
          visited += wallNo
        }
        // 次の壁の始点＝前の壁の終点
        val nextStart = (if(wallDir == 1) wall.to else wall.from)
        // {次の壁の始点 -> つながっている壁|not in 両方水の壁 && 崩壊壁}から「角度」の小さい順にたどる
        //println(nextStart)
        val wallAry = point2wallAry(nextStart)
        var minArg = Integer.MAX_VALUE
        var minWallDir:(Wall,int) = null
        for(i <- 0 until (wallAry.length)) {
          val nextWallDir = wallAry(i)
          //println("nextWallDir = " + nextWallDir)
          if(nextWallDir != null && !bothWater.contains(nextWallDir._1.no) && 
            !brokenWall.contains(nextWallDir._1.no)) {
            // 角度＝外積（前の壁、次の壁）×左手に水（正負）-> ９０～３６０
            def getArg(wall1:Wall, wallDir1:int, wall2:Wall, wallDir2:int, isLeftWater:int):int = {
              def toSign(p:Point):Point = Point(toSignI(p.x), toSignI(p.y))
              def toSignI(i:int) = if(i<0) -1 else if(i==0) 0 else 1
              def toVec(wall:Wall, wallDir:int) =
                if(wallDir == 1) Point(wall.to.x - wall.from.x, wall.to.y - wall.from.y)
                else Point(wall.from.x - wall.to.x, wall.from.y - wall.to.y)
              val vec1 = toSign(toVec(wall1, wallDir1))
              val vec2 = toSign(toVec(wall2, wallDir2))
              if(vec1 == vec2) return 180
              else if(vec1.x == -vec2.x && vec1.y == -vec2.y) return 360
              val gaiseki = (vec1.x * vec2.y - vec1.y * vec2.x) * isLeftWater
              if(gaiseki < 0) return 90
              else return 270
            }
            val arg = getArg(wall, wallDir, nextWallDir._1, nextWallDir._2, isLeftWater)
            //println("arg = " + arg)
            if(arg < minArg) {
              minArg = arg
              minWallDir = nextWallDir
            }
          }
        }
        //assert(minWallDir != null)
        if(minWallDir == null) return
        // 最初の壁に戻って来たら終了
        val nextWall = minWallDir._1
        val nextWallDir = minWallDir._2
        if(nextWall.no == firstWallNo && nextWallDir == firstWallDir) return
        wall = nextWall
        wallDir = nextWallDir
        wallNo = wall.no
      }
      
    }
    loop()
    brokenWall ++= visited
    visited.clear
  }  
  println(bothWater.size)
  for(wallNo <- bothWater)
    println(wallMap(wallNo).no)
  //println(brokenWall.size)
}