2005Bの解答
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
|
ログイン
]
開始行:
[[ACM/ICPC]]&br;
&br;
&br;
[[2005Bの問題:http://www.acm-japan.org/past-icpc/domestic2005/B/B_ja.html]]&br;
&br;
&br;
回答者:[[ほへい]]&br;
&br;
解法:すべての線を原点に移動し、最初の線が上を向くようにする。&br;
点の数が等しければ座標を比較する。&br;
結果が偽なら座標をひっくり返して同じ操作をする&br;
&br;
所要時間:80分&br;
&br;
速度:データセット瞬殺&br;
&br;
実行環境:PenM 1.6GHz 512M Win2000&br;
&br;
&br;
備考:構造体使用のものに変更。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");
}
終了行:
[[ACM/ICPC]]&br;
&br;
&br;
[[2005Bの問題:http://www.acm-japan.org/past-icpc/domestic2005/B/B_ja.html]]&br;
&br;
&br;
回答者:[[ほへい]]&br;
&br;
解法:すべての線を原点に移動し、最初の線が上を向くようにする。&br;
点の数が等しければ座標を比較する。&br;
結果が偽なら座標をひっくり返して同じ操作をする&br;
&br;
所要時間:80分&br;
&br;
速度:データセット瞬殺&br;
&br;
実行環境:PenM 1.6GHz 512M Win2000&br;
&br;
&br;
備考:構造体使用のものに変更。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");
}
ページ名: