ARCTIC 질문드립니다

  • kws4679
    kws4679

    ARCTIC 입니다

    종만님의 소스를 통해서 랜덤 제네레이션으로

    테스트를해보았는데도 틀린답을 찾을수가 없어서

    이렇게 질문드립니다.

    종만님의 코드와 동일하게 이분법을 이용하였고

    특정 거리 를 방문 가능한지 판단하는 코드는

    처음부터 순회하면서 방문가능한기지를 찾고

    해당 기지에 대해 다시 재귀적으로 처리한후

    마지막으로 모두 방문되었는지 확인하였습니다...

    흑 답안을 보고도 모르는 느낌이라 좌절스럽네요 ㅠㅠ

    #include <iostream>
    #include <vector>
    #include <cstring>
    #include <math.h>
    #include <algorithm>
    using namespace std;
    pair<double,double> camps[101];
    bool visit[101];
    int n;
    double x,y;
    double getDistance(int i, int j){
        return sqrt(pow(camps[i].first-camps[j].first,2)+pow(camps[i].second-camps[j].second,2));
    }
    void possible(int index, double dist){
        for(int i=0;i<n;++i)
            if(i!=index && !visit[i] && getDistance(index,i)<=dist) {
                visit[i]=true;
                possible(i,dist);
            }
    }
    bool upper(int index, double dist){
        memset(visit, 0, sizeof(visit));
        visit[0] = true;
        possible(0,dist);
        bool can = true;
        for(int i=0;i<n;++i)
            if(!visit[i]) can = false;
        return can;
    }
    int main(){
        int c;
        scanf("%d", &c);
        while(c--){
            scanf("%d", &n);
            for(int i=0;i<n;++i){
                scanf("%lf %lf", &x,&y);
                camps[i] = pair<double,double>(x,y);
            }
            vector<double> dists;
            for(int i=0;i<n;++i)
                for(int j=0;j<n;++j)
                    dists.push_back(getDistance(i,j));
            sort(dists.begin(), dists.end());
            int lo=0,hi=dists.size()-1;
            while(lo<hi){
                int mid=(lo+hi)/2;
                if(mid==lo) {
                    if(!upper(0,dists[mid])) lo = hi;
                    break;
                } else {
                    if(upper(0,dists[mid])) hi=mid;
                    else lo=mid;
                }
            }
            printf("%.02lf\n",dists[lo]);
        }
        return 0;
    }
    

    잘 부탁드립니다 ㅠㅠ


    10년 전
1개의 댓글이 있습니다.
  • JongMan
    JongMan

    -O3 옵션을 넣고 컴파일해 보니까 제 컴퓨터에서는 세그폴트가 뜨는군요. 릴리즈 모드에서 랜덤 데이터를 한번 돌려보세요.


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