ARCTIC 문제 질문입니다. kobeng 안녕하세요 처음 가입해보고 문제를 풀어보았습니다. 예제를 실행했을때는 정상적으로 정답이 출력이 됩니다. 출력의 방식이 잘못된것인가요?? 알고리즘을 계속 들여다 봐도 오류는 없는 것 같아 질문드립니다. #include <stdio.h> #include <stdlib.h> #include <math.h> #define MAX_TEST_CASE 50 #define MAX_NUM_GIJI 100 typedef struct _Giji{ double x; double y; int isConnect; }Giji; double distance(Giji d1,Giji d2); int isAllConnect(Giji *giji,int n,double power); void connect(Giji center,int n,Giji *giji,double power); int main(void){ int c,n; int i,j; double max_distance=0,temp=0; double left_power=0,right_power=0,power=0; int state=0; double result[MAX_TEST_CASE]; Giji giji[MAX_NUM_GIJI]; scanf("%d",&c); //테스트 케이스 수 세기 if(c>MAX_TEST_CASE){ //예외처리 printf("error\n"); exit(0); } for(i=0;i<c;i++){ temp=0; max_distance=0; scanf("%d",&n); //기지 수 설정 if(n>MAX_NUM_GIJI){ //예외처리 printf("input error\n"); exit(0); } for(j=0;j<n;j++){ //기지 좌표 설정 scanf("%lf%lf",&giji[j].x,&giji[j].y); if((giji[j].x<0||giji[j].x>1000)&&(giji[j].y<0||giji[j].y>1000)){ //예외처리 printf("input error\n"); exit(0); } } giji[0].isConnect=1; //0번은 기지본부 for(j=1;j<n;j++){ //본부와의 최대길이 측정 temp=distance(giji[0],giji[j]); if(max_distance<temp) max_distance=temp; } /*binary search비슷하게 찾는다. *|-----------------------------| *0 MAX *|--------------|--------------| * state=allconnect *|-------|------|--------------| * state=notallconnnect *|-------|---|--|--------------| * loop돌면서 소수셋째자리까지 같으면 멈춤 */ right_power=max_distance; while((right_power-left_power)>0.001){ power =(right_power+left_power)/2.; state=isAllConnect(giji,n,power); if(state==1) //allconnect right_power=power; else if(state==0) //notallconnect left_power=power; } result[i]=power; } for(i=0;i<c;i++) printf("%.2lf\n",result[i]); return 0; } int isAllConnect(Giji *giji,int n,double power){ int i; int state=1; for(i=1;i<n;i++){ //연결상태 초기화 giji[i].isConnect=0; } connect(giji[0],n,giji,power); //거리가 power안에있는 것들 다 연결 for(i=0;i<n;i++){ //다연결되었는지 확인 if(giji[i].isConnect==0){ //연결이 안되어 있으면 state=0 state=0; break; } } return state; } void connect(Giji center,int n,Giji *giji,double power){ int i; for(i=0;i<n;i++){ if(giji[i].isConnect==0&&(distance(center,giji[i])<=power)){ giji[i].isConnect=1; connect(giji[i],n,giji,power); } } } double distance(Giji d1,Giji d2){ double x,y; if(d2.x>d1.x) x=d2.x-d1.x; else x=d1.x-d2.x; if(d2.y>d1.y) y=d2.y-d1.y; else y=d1.y-d2.y; return sqrt(x*x+y*y); } 11년 전
2개의 댓글이 있습니다. JongMan 초기화 문제가 있네요. 테스트 케이스가 여러 개 있는 입력을 만들어 넣어 보세요. 11년 전 link kobeng 앗 문제점 찾았네요ㅜㅜ 이런간단한 문제였다니 감사합니다! 11년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
kobeng
안녕하세요 처음 가입해보고 문제를 풀어보았습니다.
예제를 실행했을때는 정상적으로 정답이 출력이 됩니다.
출력의 방식이 잘못된것인가요??
알고리즘을 계속 들여다 봐도 오류는 없는 것 같아 질문드립니다.
11년 전