2004Dの解答

ACM/ICPC


2004Dの問題


回答者：ほへい

方針：最大数の点を囲める円を描くとき、そのうちの二点を円周上に含む円が必ず存在する

所要時間：２〜３時間

速度：300個の点で１秒程度
　　　サンプルインプット…1秒弱
　　　データセット…１つにつき20秒弱

実行環境：PenM 1.6GHz 512M Win2000

#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;
}