DouKaku?

object Flood2 extends Application {
  val N = readInt
  val dots = Map(List.tabulate(N, i => {
    val line = readLine.split(" ").map(Integer.parseInt(_)).toList
    (i+1, (line(0), line(1)))
  }):_*)
  val W = readInt
  val initWalls = List.tabulate(W, i => (i+1) :: readLine.split(" ").map(Integer.parseInt(_)).toList)
  
  def step(walls:WallList, prevHasWater:WaterMap) {
    val hasWater = searchWater(walls, prevHasWater)
    val leftWall = getLeftWall(walls, hasWater)
    if(isDone(leftWall, hasWater)) {
      printResult(leftWall)
      exit
    }
    step(leftWall, hasWater)      
  }
  step(initWalls, initHasWater)

  def initHasWater() = {
    Map(initWalls.map(wall => {
      (wall(0), (false, false))
    }):_*)
  }
  
  // 0 = 壁番号,　1 = from, 2 = to
  type Wall = List[int]
  type WallList = List[Wall]
  type WaterMap = Map[int, (boolean, boolean)]
  type Point = int
  // 壁番号, from, to
  type WallDir = (int,Point,Point)
  
  def searchWater(walls:WallList, hasWater:WaterMap) : WaterMap = {
    val haveToVisit = getHaveToVisit(walls, hasWater)
    val startWall = getStartWall(walls, haveToVisit)
    def step(checkWall:WallDir, startWall:WallDir, hasWater:WaterMap, haveToVisit:Set[Point], isLeftWater:Boolean):WaterMap = {
      if(checkWall == null) return hasWater
      // nextWall探す
      val wallList = getWalls(walls, checkWall._3)
      val nextWallList = wallList.sort((w1, w2) => getArg(checkWall, w1, isLeftWater) < getArg(checkWall, w2, isLeftWater))
      var nextWall = nextWallList(0)
      // hasWater を更新
      val checkWallNo = checkWall._1
      val water = hasWater(checkWallNo)
      val wall = getWall(walls, checkWallNo)
      val nextHasWater = (hasWater(checkWallNo) = 
        if(wall(1) == checkWall._2) (true, water._2) else (water._1, true))
      // haveToVisit から減らす
      val nextHaveToVisit = (haveToVisit - checkWall._1 - checkWall._2)
      if(nextWall == startWall)
        return nextHasWater
      return step(nextWall, startWall, nextHasWater, nextHaveToVisit, isLeftWater)
    }
    step(startWall, startWall, hasWater, haveToVisit, calcIsLeftWater(startWall))
  }
  
  def calcIsLeftWater(wall:WallDir) = dots(wall._2)._1 != dots(wall._3)._1 
  
  def getArg(baseWall:WallDir, checkWall:WallDir, isLeftWater:boolean):int = {
    assert(baseWall._3 == checkWall._2)
    // baseWall を逆向きにして 90~360度の時計周りの角度を求める
    val baseVec = toVec(minus(dots(baseWall._2), dots(baseWall._3)))
    val checkVec = toVec(minus(dots(checkWall._3), dots(checkWall._2)))
    if(baseVec == checkVec) return 360
    val naiseki = (baseVec._1 * checkVec._2 - baseVec._2 * checkVec._1)
    if(naiseki == 0) return 180
    else if(naiseki > 0 ^ !isLeftWater) return 90
    else return 270
  }
  
  def minus(p1:(int,int), p2:(int,int)) = (p1._1 - p2._1, p1._2 - p2._2)
  def toVec(xy:(int,int)) = (toDir(xy._1), toDir(xy._2))
  def toDir(v:int) = { if(v == 0) 0 else v / Math.abs(v) }
  
  def getWalls(walls:WallList, startPoint:Point):List[WallDir] = {
    walls.filter(wall => {
      wall(1) == startPoint || wall(2) == startPoint      
    }).map(wall => {
      if(wall(1) == startPoint)
        (wall(0), wall(1), wall(2))
      else
        (wall(0), wall(2), wall(1))
    })
  }
  
  def getWall(walls:WallList, no:int):Wall = {
    walls.find(wall => wall(0) == no).get
  }
  
  def getHaveToVisit(walls:WallList, hasWater:WaterMap) : Set[Point] = {
    // 水のついてない壁のリスト
    val nonWaterList = walls.filter(wall => {
      hasWater(wall(0)) != (true, true)
    })
    // 点のリストに変換
    Set(List.flatten(nonWaterList.map(wall => List(wall(1), wall(2)))):_*)
  }
  
  def getStartWall(walls:WallList, haveToVisit:Set[Point]) : WallDir = {
    if(haveToVisit.size == 0) return null
    // 左上の点を探す
    val p = haveToVisit.toList.sort((p1, p2) => {
      val xy1 = dots(p1)
      val xy2 = dots(p2)
      xy1._2 < xy2._2 || (xy1._2 == xy2._2 && xy1._1 < xy2._1) 
    }).head
    // その点を含む壁を探す
    val wall = walls.find(wall => {
      wall(1) == p || wall(2) == p 
    }).get
    if(wall(1) == p) (wall(0), wall(1), wall(2))
    else (wall(0), wall(2), wall(1))
  }
  
  def getLeftWall(walls:WallList, hasWater:WaterMap) = {
    walls.filter(wall => {
      val water = hasWater(wall(0))
      water._1 == water._2
    })
  }
  
  def isDone(walls:WallList, hasWater:WaterMap):boolean = {
    walls.foreach(wall => {
      val water = hasWater(wall(0))
      if(!water._1 || !water._2) return false 
    })
    true
  }
  
  def printResult(walls:WallList) {
    println(walls.length)
    walls.foreach(w => println(w(0)))
  }
}

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)
}