[問題] Google Code Jam 2009, Round 2 - D

[RockLee (Now of all times)]

題目敘述網址:
http://code.google.com/codejam/contest/204113/dashboard#s=p3&a=3

官方解答說明:
http://code.google.com/codejam/contest/204113/dashboard#s=a&a=3

看了當初參賽者上傳的 code 才知道 large dataset 怎麼解.
想要請教版上高手的是, 當遇到需要用到浮點數的運算時,
要如何決定合理的 epsilon 值呢?

以這題為例, 在判斷某一個 midR 是否為一個足夠大的半徑時,
可能的判斷方式為:

for (int i = 0; i < candidate.size() && !valid; i++)
for (int j = i; j < candidate.size() && !valid; j++)
{
 Point c1 = candidate.get(i);
 Point c2 = candidate.get(j);

 valid = true;

 for (Circle p : plant)
 {
  double epsilon = 1e-10;

  if (midR + epsilon < p.radius) {valid = false; break;}

  if (c1.distanceSquare(p.center) > Math.pow((midR + epsilon - p.radius), 2))
  if (c2.distanceSquare(p.center) > Math.pow((midR + epsilon - p.radius), 2))
  {valid = false; break;}
 }
}

以實驗的結果來說, epsilon 的值設為 1e-4 ~ 1e-13 跑出來的結果都正確,
但設為多少比較合理呢?

[小弟練習的 implementation in Java]
import java.io.*;
import java.util.*;

class D
{
 private static BufferedReader input;
 private static BufferedWriter output;

 public static void main(String[] args)
 {
  try
  {
   input = new BufferedReader(new FileReader(args[0]  + ".in"));
   output = new BufferedWriter(new FileWriter(args[0] + ".out"));

   String line = input.readLine();
   int testcases = getInt(line, 0);

   for (int testcase = 1; testcase <= testcases; testcase++)
   {
    line = input.readLine();
    int N = getInt(line, 0);

    Circle[] plant = new Circle[N];
    for (int i = 0; i < N; i++)
    {
     line = input.readLine();
     plant[i] = new Circle(getInt(line, 0), getInt(line, 1), getInt(line, 2));
    }

    double minR = 0, maxR = 10000;
    while ((maxR - minR) > 1e-6)
    {
     double midR = (maxR + minR) / 2;
     boolean valid = false;

     ArrayList<Point> candidate = new ArrayList<Point>();

     for (Circle c : plant) {candidate.add(c.center);}

     for (int i = 0; i < N; i++)
     for (int j = i + 1; j < N; j++)
     {
      Circle c1 = new Circle(plant[i].center, midR - plant[i].radius);
      Circle c2 = new Circle(plant[j].center, midR - plant[j].radius);
      for (Point p : c1.intersectPoints(c2)) {candidate.add(p);}
     }

     for (int i = 0; i < candidate.size() && !valid; i++)
     for (int j = i; j < candidate.size() && !valid; j++)
     {
      Point c1 = candidate.get(i);
      Point c2 = candidate.get(j);

      valid = true;

      for (Circle p : plant)
      {
       double epsilon = 1e-10;

       if (midR + epsilon < p.radius) {valid = false; break;}

       if (c1.distanceSquare(p.center) > Math.pow((midR + epsilon -
p.radius), 2))
       if (c2.distanceSquare(p.center) > Math.pow((midR + epsilon -
p.radius), 2))
       {valid = false; break;}
      }
     }

     if (valid) {maxR = midR;}
     else {minR = midR;}
    }

    String result = "Case #" + testcase + ": " + minR;
    output(result);
   }

   input.close();
   output.close();
  }
  catch (Exception e)
  {
   e.printStackTrace();
  }
 }

 public static int getInt(String line, int index)
 {return Integer.parseInt(getString(line, index));}

 public static String getString(String line, int index)
 {
  line = line.trim();
  while (index > 0) {line = line.substring(line.indexOf(' ') + 1); index--;}

  if ((-1) == line.indexOf(' ')) {return line;}
  else {return line.substring(0, line.indexOf(' '));}
 }

 public static void output(String s) throws Exception
 {
  System.out.println(s);
  output.write(s);
  output.newLine();
 }
}

class Point
{
 public final double x, y;

 public Point(double x, double y) {this.x = x; this.y = y;}

 public double distanceSquare(Point another)
 {return (Math.pow((this.x - another.x), 2) + Math.pow((this.y - another.y),
2));}

 public double distance(Point another)
 {return Math.hypot((this.x - another.x), (this.y - another.y));}
}

class Circle
{
 public final Point center;
 public final double radius;

 public Circle(Point c, double r) {center = c; radius = r;}
 public Circle(double x, double y, double r) {center = new Point(x, y);
radius = r;}

 public Point[] intersectPoints(Circle another)
 {
  Point c0 = this.center;
  Point c1 = another.center;
  double r0 = this.radius;
  double r1 = another.radius;
  double d = c0.distance(c1);

  if (c0.x == c1.x && c0.y == c1.y) {return new Point[0];}
  if (d > r0 + r1) {return new Point[0];}
  if ((d + r0) < r1) {return new Point[0];}
  if ((d + r1) < r0) {return new Point[0];}

  // http://paulbourke.net/geometry/2circle/

  double a = (r0 * r0 - r1 * r1 + d * d) / (2 * d);
  double h = Math.sqrt(r0 * r0 - a * a);
  double x2 = c0.x + a * (c1.x - c0.x) / d;
  double y2 = c0.y + a * (c1.y - c0.y) / d;

  Point[] intersects = new Point[2];

  intersects[0] = new Point(x2 + h * (c1.y - c0.y) / d, y2 - h * (c1.x -
c0.x) / d);
  intersects[1] = new Point(x2 - h * (c1.y - c0.y) / d, y2 + h * (c1.x -
c0.x) / d);

  return intersects;
 }
}

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 59.126.30.95
推 DJWS:比大小的時候通常不需要eps  因為誤差加誤差就是更大的誤差
→ DJWS:判斷等於的時候可以設eps  因為一定有誤差導致等於變成不等於
→ DJWS:eps大小則是根據浮點數運算誤差決定  double可以存個15位數
→ DJWS:對於一般的問題來說足夠精準  eps意思意思設個數字就可以了
→ RockLee:感謝 D 大的經驗分享～
→ RockLee:順便分享一下我在「培養與鍛鍊程式設計的邏輯腦」中
→ RockLee:看到的作者的經驗分享：（以下摘錄自該書 P260）
→ RockLee:通常在比較包含誤差的浮動小數點值時，
→ RockLee:都必須使用適當小的數 EPS，寫成下面這樣
→ RockLee:a < b → a + EPS < b
→ RockLee:a <= b → a < b + EPS
→ RockLee:a == b → abs(a - b) < EPS