1981 Circle and Points

「1981 Circle and Points」の編集履歴（バックアップ）一覧はこちら

「1981 Circle and Points」(2006/04/17 (月) 01:55:35) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

**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);
     }
 }