장장 7시간 정도 걸려서 푼 문제다..
문제해법을 고민하는데 1/3정도는 고민을 한 듯..
sin, cos같은 함수를 안본지가 꽤나 오래돼고.. 원넓이 구하는 공식같은거도 기억이 안나서 찾아보면서 풀었다.
문제 요지는 파리채 구멍 영역중 파리의 중심이 위치했을때 살 수 있는 면적을 구하는 문제.
파리채의 왼쪽아래좌표와 오른쪽 위 좌표를 구해서, 면적의 모양에 따라 일일이 구해주면서 풀었다.
음 그런데. 예시의 내용이나 Smaill.in은 맞게 나오는데, Large.in을 넣으면 InCorrect가 뜬다.
무슨 이유일까 싶어 고민해 봤지만, 구체적으로 머가 틀리다는 건지가 안나와서 그냥 스킵하기로..
소스파일
#include <stdio.h>
#include <string.h>
#include <stdlib.h>#define SQ(X) ((X)*(X))
#define INPUT_SIZE 100000
#define X_COUNT 3000
double PI = 3.14159265358979323846264;
double x1[X_COUNT][X_COUNT];
double y1[X_COUNT][X_COUNT];
double x0[X_COUNT][X_COUNT];
double y0[X_COUNT][X_COUNT];
double dis1[X_COUNT][X_COUNT];
double dis0[X_COUNT][X_COUNT];
double dis_10[X_COUNT][X_COUNT];
double dis_01[X_COUNT][X_COUNT];
int main() {FILE *fp;
char sLine[INPUT_SIZE];
int loop_cnt;
int i, j, k;
char delim[] = "' '";
char *token_str;
double f, R, t, r, g;
double interval, real_R, sqrt_R;
int x_count;
//fp = fopen("small.in", "r");
fp = fopen("large.in", "r");if(fp == NULL){
printf("can't read file\n");
return 0;
}
fgets(sLine, INPUT_SIZE, fp);
loop_cnt = atoi(sLine);
for( i = 0; i < loop_cnt; i++)
{
double hole = 0;
double total_area = 0;
fgets(sLine, INPUT_SIZE, fp);
f = atof(strtok(sLine, delim));
R = atof(strtok(NULL, delim));
t = atof(strtok(NULL, delim));
r = atof(strtok(NULL, delim));
g = atof(strtok(NULL, delim));
interval = g+r+f;
real_R = R - t - f;
x_count = real_R / interval + 1;total_area = R * R * PI / 4;
for(j=0; j < x_count; j++)
{
for(k=0; k< x_count; k++)
{
x1[j][k] = g * (j+1) + 2 * j * r + r - f;
y1[j][k] = g * (k+1) + 2 * k * r + r - f;
x0[j][k] = r + j * (g + 2 * r ) + f;
y0[j][k] = r + k * (g + 2 * r ) + f;
dis1[j][k] = sqrt(SQ(x1[j][k]) + SQ(y1[j][k]));
dis0[j][k] = sqrt(SQ(x0[j][k]) + SQ(y0[j][k]));dis_10[j][k] = sqrt(SQ(x1[j][k]) + SQ(y0[j][k]));
dis_01[j][k] = sqrt(SQ(x0[j][k]) + SQ(y1[j][k]));
if(dis1[j][k] > real_R && dis0[j][k] > real_R ){
}else if(dis1[j][k] > real_R && dis0[j][k] < real_R ){
double l_height = 0, l_width = 0, r_height = 0, r_width = 0, theta = 0;
if(dis_10[j][k] < real_R && dis_01[j][k] < real_R){
l_height = sqrt( SQ(real_R) - SQ(x1[j][k])) - y0[j][k];
l_width = x1[j][k] - sqrt(SQ(real_R) - SQ(y1[j][k]));
r_height = y1[j][k] - sqrt(SQ(real_R) - SQ(x1[j][k]));
r_width = sqrt(SQ(real_R) - SQ(y1[j][k])) - x0[j][k];
if(l_height > 0 && l_width > 0) hole += l_height * l_width;
if(r_height > 0 && r_width > 0) hole += r_height * r_width;
if(r_width > 0 && l_height > 0) hole += r_width * l_height;
if(l_width > 0 && r_height > 0) hole += l_width * r_height / 2;
theta = asin(y1[j][k] / real_R) - acos(x1[j][k] / real_R);
hole += real_R*real_R*theta/2 - (real_R*sin(theta)*real_R)/2;
}
else if(dis_10[j][k] < real_R && dis_01[j][k] >= real_R){
l_height = sqrt( SQ(real_R) - SQ(x1[j][k])) - y0[j][k];
l_width = x1[j][k] - x0[j][k];
r_height = sqrt(SQ(real_R) - SQ(x0[j][k])) - sqrt(SQ(real_R) - SQ(x1[j][k]));
if(l_height > 0 && l_width > 0) hole += l_height * l_width;
if(r_height > 0 && l_width > 0) hole += r_height * l_width / 2;
theta = acos(x0[j][k] / real_R) - acos(x1[j][k] / real_R);
hole += SQ(real_R)*theta/2 - (real_R*sin(theta)*real_R)/2;
}
else if(dis_10[j][k] >= real_R && dis_01[j][k] < real_R){
r_width = sqrt(SQ(real_R) - SQ(y1[j][k])) - x0[j][k];
r_height = y1[j][k] - y0[j][k];
l_width = sqrt( SQ(real_R) - SQ(y0[j][k])) - sqrt(SQ(real_R) - SQ(y1[j][k]));
if(r_height > 0 && r_width > 0) hole += r_height * r_width;
if(r_height > 0 && l_width > 0) hole += r_height * l_width/ 2;
theta = asin(y1[j][k] / real_R) - asin(y0[j][k] / real_R);
hole += SQ(real_R)*theta/2 - (real_R*sin(theta)*real_R)/2;
}
else{
l_width = sqrt( SQ(real_R) - SQ(y0[j][k])) - x0[j][k];
l_height = sqrt( SQ(real_R) - SQ(x0[j][k])) - y0[j][k];
if(l_height > 0 && l_width > 0) hole += l_height * l_width/ 2;
theta = acos(x0[j][k] / real_R) - asin(y0[j][k] / real_R);
hole += SQ(real_R)*theta/2 - (real_R*sin(theta)*real_R)/2;
}
}
else{
hole += (x1[j][k] - x0[j][k]) * ( y1[j][k] - y0[j][k]);
}
}
}
printf("Case #%d: %.6f\n", i+1, fabs(1 - ( hole / total_area)));
}
return 0;
}