6개의 댓글이 있습니다.
-
-
ggabu420 -
아;;; 실수했네요.. 왜 직접 r을 체크하지 않았었지; 감사합니다!
그런데 음 고쳐도 여전히 오답이 나네요..
다른 예외는 이제 왠지 없을거같은데 이제 로직문제인걸지..
ㅠㅠ 정말 이 문제가 절 죽이네요.그 외에 방금 코드에 사소한 문제 하나를 발견해서
수정하긴 했습니다만 그래도 역시 오답이네요.................#include <iostream> #include <vector> #include <algorithm> #include <cmath> #define PI 3.1415926535897932 using namespace std; double GetAngle(double cx1, double cy1, double cx2, double cy2) { double ln,t; ln = sqrt((cx2-cx1)*(cx2-cx1) + (cy2-cy1)*(cy2-cy1)); t = asin(ln/16.0)+asin(ln/16.0); return t; } int main() { int i,j,k,n,ch,cnt,mn,idx; double x,y,r,ta,tb,tc,mx,sum; vector<pair<double,pair<double,double>>> vpr,tvpr; pair<double,pair<double,double>> pr; cin >> ch; for( i = 0; i < ch; i++ ){ vpr.clear(); scanf("%d",&n); for( j = 0; j < n; j++ ){ cin >> y >> x >> r; vpr.push_back(make_pair(r,make_pair(x,y))); } tvpr = vpr; if( vpr.size() == 1 ){ if( vpr[0].first >= 16.0 ) cout << 1 << endl; else cout << "IMPOSSIBLE" << endl; continue; } else{ idx = -1; for( j = 0; j < vpr.size(); j++ ){ if( vpr[j].first >= 16.0 ){ cout << 1 << endl; idx = 0; break; } } if( !idx ) continue; } mn = 1000; for( k = 0; k < tvpr.size(); k++ ){ vpr = tvpr; pr = vpr[k]; vpr.erase(vpr.begin()+k); cnt = 1; sum = 4.0*asin(pr.first/16.0); while(1){ mx = 0; idx = -1; for( j = 0; j < vpr.size(); j++ ){ ta = 2.0*asin(pr.first/16.0); tb = 2.0*asin(vpr[j].first/16.0); tc = GetAngle(pr.second.first,pr.second.second,vpr[j].second.first,vpr[j].second.second); if( ta+tb >= tc ){ if( abs(ta-tb) <= tc ){ if( mx <= tb+tc-ta ){ mx = max(mx,tb+tc-ta); idx = j; } } } } if( idx != -1 ){ cnt++; sum += mx; pr = vpr[idx]; vpr.erase(vpr.begin()+idx); if( sum >= 2.0*PI ) break; if( vpr.size() == 0 ){ idx = -1; break; } } else break; } if( idx != -1 ) mn = min(mn,cnt); } if( mn == 1000 ) cout << "IMPOSSIBLE" << endl; else cout << mn << endl; } return 0; }
11년 전 link
-
-
-
ggabu420 -
감사합니다. 여러모로 귀찮으실 것 같지만 일단 설명해보겠습니다..
단순히 모든 점을 시작 기준점으로 놓고(for k 문)
그 하나하나의 점에서 그 점을 제외하고 감시 범위가 겹치는
점들을 찾아 그 두 감시 범위를 합쳐서 가장 멀리까지 감시하는
점을 찾습니다. 이 과정은 for j 에서 하나하나 점들을 검사합니다.그리고 찾았을 경우 그 점을 vector 에서 지우고,
다시 이번엔 지운 그 점을 기준점으로 하여(pr = vpr[idx])
똑같이 반복합니다.
점을 vector에서 하나 지울때마다 카운터를 증가시킵니다.
만약 조건에 맞는 점을 못찾았을 경우 그냥 break 해서 나오고
다른 점을 첫 기준점으로 찾습니다.(for k문 다음으로 넘어간다는 의미)이렇게 반복하면서 감시 범위를 쭉 모두 sum에 더하여,
감시 범위는 라디안 단위로 저장하고 있어서 합이 2pi 가
넘으면 원 전체를 감시하는 것으로 생각하여 나옵니다.그리고 이 카운터의 최소값을 mn 에 min() 해가면서 찾습니다.
이런 식으로 for k 가 다 돌아가면 카운터 최소값이 저장됩니다.GetAngle() 함수는 원 위의 두 점 사이의 호의 각을 얻습니다.
그냥 한 점의 감시 범위각은 4asin(r/16) 로 얻습니다.
코드의 전체적인 구성은 대략적으로 이러합니다..맞는 답 반 틀린 답 반이면 뭔가 크게 잘못된 듯 한데
제가 특정 케이스에 맞춰서 로직을 구성해서 그런게 아닌가 싶네요..ㅠ
11년 전 link
-
-
-
JongMan -
음.. 제가 정확하게 돌려보거나 한건 아니지만요. 매번 pr에 저장된 마지막 기준점만을 생각하시잖아요? 예를 들어
a, b, c, d 세 개의 점이 있는데, 이들이 덮는 구간이 각각 라디안 기준으로 [0, 1] [0.5, 1.5] [0, 0.6] [1.5, 1.6]이라고 하지요.
a가 기준으로 시작되었다고 하면 b를 선택하고 b를 기준점으로 잡으시겠죠. 그런데 그 후에는 c는 아무 의미가 없는데도 c를 선택하시는 것 아닌가요? c는 a에 포함되어 있으니 사실상 아무 소용이 없는데 sum에 0.5가 더해지죠.
11년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
ggabu420
이 문제에 보면 초소의 감시 범위가 16.001 까지라고 되어있습니다.
그러면 만약 한 초소의 감시 범위가 16.0 인 것이 하나라도
있다면 답은 무조건 1이 되는 것인가요?
(즉 16.0 "이상" 이면 전체를 감시한다고 봐도 되나요?)
이 16.001 이라는 게 그다지 중요한건 아니죠?
음... 그리고 좀 염치없지만 이 문제를 일주일 넘게
잡고 있었습니다만 분명 맞다고 생각되는 코드인데 계속
오답이 뜨네요.. 혹시 어떤 예외를 생각못해서 코드가 아주
약간 잘못된 건지 아니면 로직상으로 큰 문제가 있는건지..
조금 복잡하지만 가능하다면 알려주시면 정말정말 감사하겠습니다.
이제 지치네요..ㅠ 작은 힌트라도 좋습니다..
당연히 예시는 잘 나오고.. 원래 문제가 있었던 부분인데
초소가 1개만 있고 16.0 이상일 때 IMPOSSIBLE 나오던 것을
귀찮아서 하드코딩해서 되게 바꿨고..
초소가 다수일 때 하나가 16.0 이상이면 무조건 답이 1이 되도록
바꾸었습니다. 그 외에는 예외를 찾지 못했습니다..
어렵네요 문제가.. 공부 더더더 많이 해야할듯...
11년 전