2005Bの解答

ACM/ICPC


2005Bの問題


回答者：ほへい

解法：すべての線を原点に移動し、最初の線が上を向くようにする。
　　　　点の数が等しければ座標を比較する。
　　　　結果が偽なら座標をひっくり返して同じ操作をする

所要時間：80分

速度：データセット瞬殺

実行環境：PenM 1.6GHz 512M Win2000


備考：構造体使用のものに変更。10分修正なんで急造っぽさは拭えませんが。

#include <stdio.h>

FILE *fp_in, *fp_out;
char *f_source = "2005B_in.txt";
char *f_answer = "2005B_out.txt";
int num_lines;

typedef struct {
   int num_points;
   int points[10][2];
} Line;

Line lines[51] = {(0)};

void setPoints(void);                // 点の座標を読み込む・sortLineの呼び出し
void sortLine(Line *ln);             // 始点が原点になるように移動・turnLineの呼び出し
void turnLine(int, int, Line *ln);   // 最初の線が上を向くように回転
int equalLines(Line ln);             // lines[0]との比較
void reverseLine(Line *ln);          // 始点〜終点を逆にする
void getAnswer(void);                // 点の数を比較・equalLines,reverseLineの呼び出し

int main(void)
{
   fp_in = fopen(f_source, "r");
   fp_out = fopen(f_answer, "w");
   
   while(1) {
       fscanf(fp_in, "%d", &num_lines);
       if(num_lines == 0) break;
       
       setPoints();
       getAnswer();
   }
   fclose(fp_out);
   fclose(fp_in);
   
   return 0;
}

void setPoints()
{
   int i, j;
   int temp[10][2];
   for(i = 0; i < num_lines + 1; i++) {
       fscanf(fp_in, "%d", &lines[i].num_points);
       for(j = 0; j < lines[i].num_points; j++) {
           fscanf(fp_in, "%d %d", &lines[i].points[j][0], &lines[i].points[j][1]);
       }
       sortLine(&lines[i]);
   }
}
   
void sortLine(Line *ln)
{
   int i;
   for(i = 1; i < ln->num_points; i++) {
       ln->points[i][0] -=ln->points[0][0];
       ln->points[i][1] -=ln->points[0][1];
   }
   ln->points[0][0] = 0;
   ln->points[0][1] = 0;
   
   if(ln->points[0][0] > ln->points[1][0]) {
       turnLine(1, -1, ln);
   }
   else if(ln->points[0][0] < ln->points[1][0]) {
       turnLine(-1, 1, ln);
   }
   else if(ln->points[0][1] > ln->points[1][1]) {
       for(i = 1; i < ln->num_points; i++) {
           ln->points[i][0] = -ln->points[i][0];
           ln->points[i][1] = -ln->points[i][1];
       }
   }
} 

void turnLine(int x, int y, Line *ln)
{
   int i, temp;
   for(i = 1; i < ln->num_points; i++) {
       temp = ln->points[i][0];
       ln->points[i][0] = x * ln->points[i][1];
       ln->points[i][1] = y * temp;
   }
} 

void reverseLine(Line *ln)
{
   int i,j, temp;
   for(i = 0; i < (ln->num_points / 2); i++) {
       for(j = 0; j < 2; j++) {
           temp = ln->points[i][j];
           ln->points[i][j] = ln->points[ln->num_points - i - 1][j];
           ln->points[ln->num_points - i - 1][j] = temp;
       }
   }
}

int equalLines(Line ln)
{
   int i;
   for(i = 0; i < ln.num_points; i++) {
       if(lines[0].points[i][0] != ln.points[i][0]) return 0;
       if(lines[0].points[i][1] != ln.points[i][1]) return 0;
   }
   return 1;
}

void getAnswer()
{
   int i;
   for(i = 1; i < num_lines + 1; i++) {
       if(lines[0].num_points == lines[i].num_points) {
           if(equalLines(lines[i])) fprintf(fp_out, "%d\n", i);
           else {
               reverseLine(&lines[i]);
               sortLine(&lines[i]);
               if(equalLines(lines[i])) fprintf(fp_out, "%d\n", i);
           }
       }
   }
   fprintf(fp_out, "+++++\n");
}