2004Dの解答
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
|
ログイン
]
開始行:
[[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;
所要時間:2〜3時間&br;
&br;
速度:300個の点で1秒程度&br;
サンプルインプット…1秒弱&br;
データセット…1つにつき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;
}
終了行:
[[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;
所要時間:2〜3時間&br;
&br;
速度:300個の点で1秒程度&br;
サンプルインプット…1秒弱&br;
データセット…1つにつき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;
}
ページ名: