Google Code Jam 2009 Round 2

ひどすぎた.

Dを見てバイナリサーチを思いついたので,まずこれを解こうとする.
スプリンクラーを置くべき位置はミンコフスキー和をとった円の交点(または円の中心)とすればよいはず.
30分ぐらいでとりあえずできるもサンプルと答えが合わない.
調べてみるとy軸と平行なときなどの例外処理がうまく行ってないとわかる.
さらに,円の交点を計算する部分に+と-のうち間違えがあったので修正などをしていると残り1時間を切っていた.
他の人の点数を見てみるとDを完答すれば通りそうだったので全力でDを解くことに.
とかなんとかしつつ,ひたすらデバッグをした結果サンプルは正しい答えを返すようになったがスモールは通らなかった.

というわけでtime up.0点だった...


結局,円の中に入っているかの判定での数値誤差が原因だった.
次のプログラムでのcheckで >1e-6 としたら通った.
幾何の怖さを改めて味わった.

import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;
import java.util.*;
import java.io.*;

public class D {
    private static final String ID = "D-large-practice";
    private static final String IN_FILE = ID+".in";
    private static final String OUT_FILE = ID+".out";
    private static final double EPS = 1e-8;
    private Scanner in;
    private PrintWriter out;
    private int cases, n;
    private double ans;
    private double[][] plants;

    private void solve(){
        double high = 1000.0;
        double low = 0.0;
        while(low+EPS<high){
            double mid = (high+low)/2;

            ArrayList<Point> ps = new ArrayList<Point>();
            for(int i=0;i<n;++i)ps.add(new Point(plants[i][0],plants[i][1]));
            for(int i=0;i<n;++i)for(int j=i+1;j<n;++j){
                    double xi = plants[i][0], yi = plants[i][1], ri = plants[i][2];
                    double xj = plants[j][0], yj = plants[j][1], rj = plants[j][2];
                    double t = (mid-rj)*(mid-rj)-(mid-ri)*(mid-ri)+xi*xi+yi*yi-xj*xj-yj*yj;
                    if(abs(xi-xj)<EPS){
                        double y = t/(2*(yi-yj));
                        double d = sqrt((mid-ri)*(mid-ri)-(y-yi)*(y-yi));
                        if(!Double.isNaN(d)){
                            ps.add(new Point(xi+d,y));
                            ps.add(new Point(xi-d,y));
                        }
                    }else if(abs(yi-yj)<EPS){
                        double x = t/(2*(xi-xj));
                        double d = sqrt((mid-ri)*(mid-ri)-(x-xi)*(x-xi));
                        if(!Double.isNaN(d)){
                            ps.add(new Point(x,yi+d));
                            ps.add(new Point(x,yi-d));
                        }
                    }else{
                        double u = -(xi-xj)/(yi-yj);
                        double v = t/(2*(yi-yj))-yi;
                        double a = 1+u*u;
                        double b = -2*xi+2*u*v;
                        double c = xi*xi+v*v-(mid-ri)*(mid-ri);
                        double d = sqrt(b*b-4*a*c);
                        if(!Double.isNaN(d)){
                            double x = (b>0)? (-b-d)/(2*a) : (-b+d)/(2*a);
                            double y = yi+v+u*x;
                            ps.add(new Point(x,y));
                            x = c/(a*x);
                            y = yi+v+u*x;
                            ps.add(new Point(x,y));
                        }
                    }
                }

            boolean isFeasible = false;
            label:for(int i=0;i<ps.size();++i)for(int j=i;j<ps.size();++j)if(check(ps.get(i),ps.get(j),mid)){
                    isFeasible = true;
                    break label;
            }     
            if(isFeasible)high=mid;
            else low=mid;
        }
        ans = low;
    }

    boolean check(Point p1, Point p2, double r){
        for(int i=0;i<n;++i){
            double xi = plants[i][0], yi = plants[i][1], ri = plants[i][2];
            if(r<ri)return false;
            if((p1.x-xi)*(p1.x-xi)+(p1.y-yi)*(p1.y-yi)-(r-ri)*(r-ri)>1e-6&&
               (p2.x-xi)*(p2.x-xi)+(p2.y-yi)*(p2.y-yi)-(r-ri)*(r-ri)>1e-6)return false;
        }
        return true;
    }

    private void read(){
        n = in.nextInt();
        plants = new double[n][3];
        for(int i=0;i<n;++i)for(int j=0;j<3;++j)plants[i][j]=in.nextInt();
    }
    private void write(){
        out.printf("Case #"+cases+": %.8f\n",ans);
        System.out.printf("Case #"+cases+": %.8f\n",ans);
    }
    private void init(){
        try{
            in = new Scanner(new File(IN_FILE));
            out = new PrintWriter(new File(OUT_FILE));
        }catch(FileNotFoundException e){ e.printStackTrace();}
    }
    private void run() {
        init();
        long start = System.currentTimeMillis();
        int n = in.nextInt();
        for(cases=1;cases<=n;++cases){
            read();
            solve();
            write();
        }
        out.close();
        long end = System.currentTimeMillis();
        System.out.println();
        System.out.println("time: "+(end-start)+"ms");
    }
    public static void main(String[] args) { new D().run();}
}
class Point{
    double x, y;
    public Point(double x, double y){
        this.x = x;
        this.y = y;
    }
    public String toString(){
        return "("+x+","+y+")";
    }
}