[[ACM/ICPC]]

[[ACM/ICPC]]&br;
&br;
&br;
[[2004Dの問題:http://www.acm-japan.org/past-icpc/domestic2004/D.jp/D.html]]&br;
&br;
&br;
回答者：[[ほへい]]&br;
&br;
方針：最大数の点を囲める円を描くとき、そのうちの二点を円周上に含む円が必ず存在する&br;
&br;
所要時間：２〜３時間&br;
&br;
速度：300個の点で１秒程度&br;
　　　サンプルインプット…1秒弱&br;
　　　データセット…１つにつき20秒弱&br;
&br;
実行環境：PenM 1.6GHz  512M  Win2000&br;
&br;
&br;

 #include <stdio.h>
 #include <math.h>
 
 
 double point[300][2];
 int num, answer;
 FILE *fp_in, *fp_out;
 char *source = "2004D_in.txt";
 char *f_ans = "2004D_out.txt";
 
 int getAnswer(void);
 void setPoint(void);
 
 int main(void)
 {
    fp_in = fopen(source, "r");
    fp_out = fopen(f_ans, "w");
    
    while(1) {
        setPoint();
        
        if(num == 0) break;
        printf("%d\n", num);
        
        answer = getAnswer();
        
        fprintf(fp_out, "%d\n", answer);
    }
    
    fclose(fp_in);
    fclose(fp_out);
    
    return 0;
 }
 
 void setPoint()
 {
    int index;
    fscanf(fp_in, "%d", &num);
    
    for (index = 0; index < num; index++) {
        fscanf(fp_in, "%lf", &point[index][0]);
        fscanf(fp_in, "%lf", &point[index][1]);
    }
 }
 
 int getAnswer()
 {
    double circle[2][2];
    int temp_answer;
    int i,j, k, l;
    double kyori;
    
    answer = 1;
    
    for(i = 0; i < num; i++) {
        for (j = i + 1; j < num; j++) {
            kyori = sqrt( pow(((point[i][0]) - (point[j][0])), 2) + pow(((point[i][1]) - point[j][1]), 2));
            
            if(kyori <= 2) {
                if(point[i][0] == point[j][0]) {
                    circle[0][0] = point[i][0] + sqrt(1 - pow(kyori / 2, 2));
                    circle[0][1] = (point[i][1] + point[j][1]) / 2;
                    
                    circle[1][0] = point[i][0] - sqrt(1 - pow(kyori / 2, 2));
                    circle[1][1] = circle[0][1];
                }
                
                else if(point[i][1] == point[j][1]) {
                    circle[0][0] = (point[i][0] + point[j][0]) / 2;
                    circle[0][1] = point[i][1] + sqrt(1 - pow(kyori / 2, 2));
                    
                    circle[1][0] = circle[0][0];
                    circle[1][1] = point[i][1] - sqrt(1 - pow(kyori / 2, 2));
                }
                
                else {
                    double tan = (point[i][1] - point[j][1]) / (point[i][0] - point[j][0]);
                    double tan2 = pow(tan, 2);
                    double derta_x = sqrt(1 - pow(kyori / 2, 2)) * sqrt(tan2 / (tan2 + 1));
                    double derta_y = sqrt(1 - pow(kyori / 2, 2)) * sqrt(1 / (tan2 + 1));
                    
                    double ave_x = (point[i][0] + point[j][0]) / 2;
                    double ave_y = (point[i][1] + point[j][1]) / 2;
                    
                    if(tan < 0) {
                        circle[0][0] = ave_x + derta_x;
                        circle[0][1] = ave_y + derta_y;
                        
                        circle[1][0] = ave_x - derta_x;
                        circle[1][1] = ave_y - derta_y;
                    }
                    else {
                        circle[0][0] = ave_x + derta_x;
                        circle[0][1] = ave_y - derta_y;
                        
                        circle[1][0] = ave_x - derta_x;
                        circle[1][1] = ave_y + derta_y;
                    }
                }
                
                
                for(l = 0; l < 2; l++) {
                    temp_answer = 2;
                    for(k = 0; k < num; k++) {
                        if(k != i && k != j) {
                            double temp = pow((circle[l][0] - point[k][0]), 2) + pow((circle[l][1] - point[k][1]), 2);
                            
                            if (temp <= 1) {
                                temp_answer++;
                            }
                        }
                    }
                    answer = (answer > temp_answer) ? answer : temp_answer;
                }
                
            }
        }
    }
    
    return answer;
 }
トップ   編集 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS