ARCTIC 문제 질문입니다.

  • kobeng
    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
    JongMan

    초기화 문제가 있네요. 테스트 케이스가 여러 개 있는 입력을 만들어 넣어 보세요.


    11년 전 link
  • kobeng
    kobeng

    앗 문제점 찾았네요ㅜㅜ 이런간단한 문제였다니 감사합니다!


    11년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.