1981 Circle and Points

1981 Circle and Points

問題

http://acm.pku.edu.cn/JudgeOnline/problem?id=1981

解答方針

「2点を通る円」をすべて列挙し，そのような円で一番多くの点を含むものを調べればよい．但し，2点を通る円が存在しない場合は，出力は1となることに注意する（1点を含む円は必ず存在する）．

2点A,Bを通る円がある点を含むかどうかチェックするとき，A,Bは無条件で「含む」と判定しなければならない点は注意を要する（中心との距離を計算して判定すると，数値誤差で「含まれない」と判定されることがある）．

解答例

import java.util.*;

public class Main{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        while(n!=0){
            Point p[] = new Point[n];
            for(int i=0;i<n;i++){
                double x = sc.nextDouble();
                double y = sc.nextDouble();
                p[i] = new Point(x,y);
            }
            
            Solver s = new Solver(n,p);
            s.solve();
            
            n = sc.nextInt();
        }
    }
}

class Solver{
    int size;
    Point point[];
    
    Solver(int n,Point p[]){
        size = n;
        point = p;
    }
    
    public void solve(){
        int c;
        c = 1;
        
        for(int i=0;i<size;i++){
            for(int j=i+1;j<size;j++){
                if(i==j) continue;
                if(point[i].dist2(point[j]) <4){
                    Point test1 = point[i].centerOfPassingCircle1(point[j],1);
                    int tmp = count(test1,i,j);
                    if(tmp>c) c = tmp;
                    Point test2 = point[i].centerOfPassingCircle2(point[j],1);
                    tmp = count(test2,i,j);
                    if(tmp>c) c = tmp;
                }
            }
        }
        System.out.println(c);
    }
    
    private int count(Point p,int i,int j){
        int c;
        c = 2;
        for(int k=0;k<size;k++){
            if(k==i || k==j) continue;
            if(p.dist2(point[k])<1) c++;
        }
        return c;
    }
}

class Point{
    double x;
    double y;
    Point(double px,double py){
        x = px;
        y = py;
    }
    public double dist2(Point p){
        return (x-p.x)*(x-p.x) + (y-p.y)*(y-p.y);
    }
    public double dist(Point p){
        return Math.sqrt(this.dist2(p));
    }
    public Point centerOfPassingCircle1(Point p,double r){
        double a = p.x - x;
        double b = p.y - y;
        double d = this.dist(p);
        double qx = x / 2 + p.x / 2 + Math.sqrt(r - d*d/4)*(-b)/d;
        double qy = y / 2 + p.y / 2 + Math.sqrt(r - d*d/4)*a/d;
        return new Point(qx,qy);
    }
    public Point centerOfPassingCircle2(Point p,double r){
        double a = p.x - x;
        double b = p.y - y;
        double d = this.dist(p);
        double qx = x / 2 + p.x / 2 - Math.sqrt(r - d*d/4)*(-b)/d;
        double qy = y / 2 + p.y / 2 - Math.sqrt(r - d*d/4)*a/d;
        return new Point(qx,qy);
    }
}