JM book에 소개 된 MINASTRITH문제 관련 질문입니다.
스스로 풀다가 잘 되지 않아 책을 참고 했고,
제 답안의 형식을 최소한으로 유지시켜보면서 책의 풀이와 맞추어보고 있는데,
문제가 풀리지 않습니다.
아주 약간의 변형을 제외하면 거의 동일 한데 어디서 오류가 발생하는 건가요?
아래 소스 코드와 주석 첨부합니다.
*주석에선 책에서의 '구간'이라는 표현을 '구간' 또는 '덮개'로 혼용하여 사용했습니다.
*실제로 실행해보면 답이 나오지 않고 모두 IMP값으로 출력됩니다.
#include<iostream>#include<vector>#include<cmath>#include<algorithm>#define PI 3.1415926//전체 영역을 커버하는 것이 불가능 할 경우 IMP를 리턴합니다.#define IMP 200000000usingnamespacestd;//초소의 위치 정보와 감시영역을 저장하는 클래스 입니다.classGuardPoint{private:doubley,x,r;public:GuardPoint(){}GuardPoint(doubleypos,doublexpos,doubleradix):y(ypos),x(xpos),r(radix){}double&GetY(void){returny;}double&GetX(void){returnx;}double&GetR(void){returnr;}};//구간을 시작점 오름차순으로 정렬 할 때 쓰일 비교함수 입니다.classCOMPARE{public:booloperator()(constpair<double,double>&r1,constpair<double,double>&r2){returnr1.first<r2.first;}};//N개의 초소를 의미합니다.intN;//변수 입력에 쓰일 임시 변수 입니다.doubleT1,T2,T3;//초소를 저장할 벡터입니다.vector<GuardPoint>GP;//초소를 구간 범위 pair로 저장할 벡터입니다.vector<pair<double,double>>I;//간단한 max함수 입니다.template<typenameT>Tbigger(constTr1,constTr2){return(r1>r2)?r1:r2;}//간단한 min함수 입니다.template<typenameT>Tsmaller(constTr1,constTr2){return(r1<r2)?r1:r2;}//초소의 정보를 구간정보로 변환 시켜주는 함수 입니다.//atan 대신 asin을 사용하였습니다.//loc은 항상 [0,2pi]를 만족하게 구해지고,range는 [0,pi]를 만족하게 구해집니다.voidmk_interval(void){doubleloc,range;for(inti=0;i<GP.size();i++){//loc가 1사분면의 각인 경우.if(GP[i].GetX()>0&&GP[i].GetY()>=0){loc=asin(GP[i].GetY()/8);}//loc가 2사분면의 각인 경우.elseif(GP[i].GetX()<=0&&GP[i].GetY()>0){loc=PI-asin(GP[i].GetY()/8);}//loc가 3사분면의 각인 경우.elseif(GP[i].GetX()<0&&GP[i].GetY()<=0){loc=PI-asin(GP[i].GetY()/8);}//loc가 4사분면의 각인 경우.else{loc=2*PI+asin(GP[i].GetY()/8);}//몇사분면이냐에 관계없이 range는 아래와 같습니다.range=2*asin(GP[i].GetR()/16);//I에 저장합니다.I.push_back(pair<double,double>(loc-range,loc+range));}return;}//동경을 나타내는 radian값 po가 주어지고, 범위가 iv로 주어질때//범위 iv를 1바퀴(2pi)만큼 변화 시켜보면서 //po가 iv에 속하는 지를 반환합니다.boolis_include(constdoublepo,constpair<double,double>&iv){boolret=false;for(inti=0;i<2;i++){if(iv.first<=po+2*PI*i&&po+2*PI*i<iv.second){ret=true;break;}}returnret;}//덮개들이 있을 때, 직선을 덮는 문제라고 생각하여 답을 내는 함수 입니다.//직선의 시작점과 종료점이 주어집니다.intmk_linear(doublesp,doubleep){intret=0,idx=0;doublebiggest;//직선이 남아 있을때 까지 반복합니다.while(sp<ep){//최대로 멀리까지 덮을 때의 끝점 값입니다.//최대값을 찾을 것이므로 처음엔 -1로 초기화 합니다.biggest=-1;//구간들을 순회합니다.//greedy choice property에 따라 idx를 0부터 순회 할 필요는 없습니다.for(;idx<I.size();idx++){//직선의 시작점이 I[idx]에 속한다면, 그들중 가장 멀리서 끝나는 덮개를 찾습니다.if(is_include(sp,I[idx])){biggest=bigger(biggest,fmod(I[idx].second,2*PI));}}//어떠한 덮개도 찾지 못했다면 IMP를 리턴합니다.if(biggest==-1){returnIMP;}//위의 논리에 맞게 sp를 수정해줍니다.sp=biggest;//하나를 사용했으니 리턴값도 1 증가 합니다.ret++;}returnret;}//답을 반환하는 함수입니다.intmk_answer(void){inttemp,ret=IMP;//모든 저장된 덮개(구간)들을 순회하면서, 아래를 실행합니다.for(inti=0;i<I.size();i++){//덮개가 0 radian을 덮는 경우if(is_include(0,I[i])){//[0,2pi]인 직선을 덮는 문제로 변형해줍니다.//mk_linear에 직선의 시작점과 종료점을 전달하여 줍니다.temp=mk_linear(fmod(I[i].second,2*PI),fmod(2*PI+I[i].first,2*PI));//그중 최솟값을 찾아줍니다.ret=smaller(ret,1+temp);}}returnret;}intmain(void){intTC;cin>>TC;while(TC--){GP.clear();I.clear();//입력을 받습니다.cin>>N;for(inti=0;i<N;i++){cin>>T1>>T2>>T3;GP.push_back(GuardPoint(T1,T2,T3));}//초소를 구간으로 변경합니다.mk_interval();//구간의 시작점 오름차순으로 정렬합니다.sort(I.begin(),I.end(),COMPARE());cout<<"ANSWER : "<<mk_answer()<<endl;}return0;}
꽤 오랜시간 여러번 확인해보았는데 어디서 틀렸는지 찾기가 힘이 듭니다 ㅠㅠ.
개인적인 생각에
1. asin계산 과정에서의 오차
2. 원을 직선으로 피는 과정에서의 범위 계산 실수
3. 책 p394
"이때는 두 구간의 중심 ~~~ 증명할 수 있습니다."
를 이해하지 못함.
셋 중하나인 것 같은데, 딱히 답을 찾지 못했습니다.
부연하여 설명드리자면, atan()은 단일 변수로 \frac{y}{x}를 받습니다. 이는 수학적인 정의에 그대로 부합하지만, 실제 각도를 계산하는 용으로 써먹기 위해서는 이를테면 y > 0, x > 0 인 경우와 y < 0, x < 0인 경우를 구분해야 합니다. 그러려면 부호를 보고 atan()의 결과를 적당히 조작해야 하는데, 이 과정이 귀찮은데다가 고려해야 할 사항도 많아 틀리기 쉬우므로 대신 atan2()를 정의하여 y와 x를 모두 받도록 한 것입니다.
canuyes
JM book에 소개 된 MINASTRITH문제 관련 질문입니다.
스스로 풀다가 잘 되지 않아 책을 참고 했고,
제 답안의 형식을 최소한으로 유지시켜보면서 책의 풀이와 맞추어보고 있는데,
문제가 풀리지 않습니다.
아주 약간의 변형을 제외하면 거의 동일 한데 어디서 오류가 발생하는 건가요?
아래 소스 코드와 주석 첨부합니다.
*주석에선 책에서의 '구간'이라는 표현을 '구간' 또는 '덮개'로 혼용하여 사용했습니다.
*실제로 실행해보면 답이 나오지 않고 모두 IMP값으로 출력됩니다.
꽤 오랜시간 여러번 확인해보았는데 어디서 틀렸는지 찾기가 힘이 듭니다 ㅠㅠ.
개인적인 생각에
1. asin계산 과정에서의 오차
2. 원을 직선으로 피는 과정에서의 범위 계산 실수
3. 책 p394
"이때는 두 구간의 중심 ~~~ 증명할 수 있습니다."
를 이해하지 못함.
셋 중하나인 것 같은데, 딱히 답을 찾지 못했습니다.
답변 기다립니다.
좋은 하루, 좋은 연말, 좋은 새해 되세요!
10년 전