Logging.scala

object Logging extends App {

  def minLogging(ref: (Int, Int), trees: Seq[(Int, Int)]): Int = {

    require(!trees.contains(ref))

    def count(s: Seq[(Int, Int)], p: ((Int, Int)) => Boolean): (Int, Int) = {
      val trues = s count p
      (trues, s.size - trues)
    }
    val (infinites, finites) = trees.map { case (x, y) => (x - ref._1, y - ref._2) }.partition(_._1 == 0)
    val (iniLeft, iniRight) = count(finites, _._1 > 0)
    val (iniFront, iniBack) = count(infinites, _._2 < 0)

    object tiltOrder extends Ordering[(Int, Int)] {
      def compare(a: (Int, Int), b: (Int, Int)): Int = a._2.toLong * b._1 compare b._2.toLong * a._1
    }

    (collection.SortedMap.empty[(Int, Int), (Int, Int)](tiltOrder) /: finites) {
      case (sortedMap, (dx, dy)) =>
        def gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
        val g = gcd(dx.abs, dy.abs)
        val tilt = (dx.abs / g, dy * dx.signum / g)
        val (front, back) = sortedMap.getOrElse(tilt, (0, 0))
        sortedMap + (tilt -> (if (dx > 0) (front + 1, back) else (front, back + 1)))
    }.foldLeft(iniLeft min iniRight, iniLeft + iniBack, iniRight + iniFront) {
      case ((min, left, right), (tilt, (front, back))) =>
        val (left1, right1) = (left - front, right - back)
        (min min left1 min right1, left1 + back, right1 + front)
    }._1
  }

  def minLogging(trees: IndexedSeq[(Int, Int)]): Seq[Int] = for { 
    i <- 0 until trees.size 
    (front, end) = trees splitAt i
  } yield minLogging(trees(i), front ++ end.tail)

  def process(lineIn: Iterator[String])(lineOut: String => Unit) =
    for (i <- 1 to lineIn.next().toInt) {
      val trees = Vector.fill(lineIn.next().toInt) {
        val Array(x, y) = lineIn.next() split ' ' map (_.toInt)
        (x, y)
      }
      lineOut(s"Case #$i:")

      for (n <- minLogging(trees)) lineOut(n.toString)
    }

  val filename = "C-large-practice"
  val writer = new java.io.PrintWriter(filename + ".out")
  try {
    process(io.Source.fromFile(filename + ".in").getLines) { s =>
      writer.println(s); writer.flush()
    }
  } finally {
    writer.flush(); writer.close()
  }
}

LoggingTest.scala

import org.scalatest._

import Logging._

class LoggingTest extends FunSuite {

  test("sample #1") {
    assert {
      minLogging(Vector((0, 0), (10, 0), (10, 10), (0, 10), (5, 5))) === Seq(0, 0, 0, 0, 1)
    }
  }

  test("sample case") {
    val input = """2
5
0 0
10 0
10 10
0 10
5 5
9
0 0
5 0
10 0
0 5
5 5
10 5
0 10
5 10
10 10""".lines

    val expected = """Case #1:
0
0
0
0
1
Case #2:
0
0
0
0
3
0
0
0
0""".lines

    lineComparison(input, expected)
  }

  test("full small") {
    val lineIn = io.Source.fromFile("C-small-practice.in").getLines()
    for (i <- 1 to lineIn.next().toInt) {
      val trees = Vector.fill(lineIn.next().toInt) {
        val Array(x, y) = lineIn.next() split ' ' map (_.toInt)
        (x, y)
      }
      assert(minLogging(trees) === minLoggingSmall(trees), s"Case #$i")
    }
  }

  test("full small case") {
    val input = io.Source.fromFile("C-small-practice.in").getLines()
    val expected = io.Source.fromFile("C-small-practice.out").getLines()

    lineComparison(input, expected)
  }

  test("full large case") {
    val input = io.Source.fromFile("C-large-practice.in").getLines()
    val expected = io.Source.fromFile("C-large-practice.out").getLines()

    lineComparison(input, expected)
  }

  def lineComparison(input: Iterator[String], expected: Iterator[String]) {
    process(input) { s =>
      for (line <- s.lines) assert(line.trim === expected.next().trim)
    }
    assert(expected.hasNext === false, "Finished too fast.")
  }

  def minLoggingSmall(x0: Int, y0: Int, trees: Seq[(Int, Int)]): Int = {

    def line(x0: Int, y0: Int, x1: Int, y1: Int): ((Int, Int)) => Double = {
      case (x, y) =>
        if (x0 == x1) x - x0
        else (y1 - y0).toDouble / (x1 - x0) * (x - x0) - (y - y0)
    }

    val result = for { (x1, y1) <- trees } yield {
      val (gt, lt) = (for {
        (x, y) <- trees if (x1, y1) != (x, y)
      } yield line(x0, y0, x1, y1)((x, y))).filter(_ != 0.0).partition(_ > 0)
      gt.size min lt.size
    }

    if (result.isEmpty) 0 else result.min
  }

  def minLoggingSmall(trees: Seq[(Int, Int)]): Seq[Int] =
    for { (x0, y0) <- trees } yield minLoggingSmall(x0, y0, trees diff Seq((x0, y0)))

}