ARCTIC 질문드립니다 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; } 잘 부탁드립니다 ㅠㅠ 11년 전
1개의 댓글이 있습니다. JongMan -O3 옵션을 넣고 컴파일해 보니까 제 컴퓨터에서는 세그폴트가 뜨는군요. 릴리즈 모드에서 랜덤 데이터를 한번 돌려보세요. 11년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
kws4679
ARCTIC 입니다
종만님의 소스를 통해서 랜덤 제네레이션으로
테스트를해보았는데도 틀린답을 찾을수가 없어서
이렇게 질문드립니다.
종만님의 코드와 동일하게 이분법을 이용하였고
특정 거리 를 방문 가능한지 판단하는 코드는
처음부터 순회하면서 방문가능한기지를 찾고
해당 기지에 대해 다시 재귀적으로 처리한후
마지막으로 모두 방문되었는지 확인하였습니다...
흑 답안을 보고도 모르는 느낌이라 좌절스럽네요 ㅠㅠ
잘 부탁드립니다 ㅠㅠ
11년 전