PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

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

看板Prob_Solve (計算數學 Problem Solving)作者RockLee (Now of all times)時間12年前 (2012/04/25 19:35)推噓1(1推 0噓 11→)

留言12則, 2人參與討論串1/1

題目敘述網址: 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