MINASTIRITH 문제 관련 질문 입니다.

  • canuyes
    canuyes

    JM book에 소개 된 MINASTRITH문제 관련 질문입니다.
    스스로 풀다가 잘 되지 않아 책을 참고 했고,
    제 답안의 형식을 최소한으로 유지시켜보면서 책의 풀이와 맞추어보고 있는데,
    문제가 풀리지 않습니다.
    아주 약간의 변형을 제외하면 거의 동일 한데 어디서 오류가 발생하는 건가요?
    아래 소스 코드와 주석 첨부합니다.

    *주석에선 책에서의 '구간'이라는 표현을 '구간' 또는 '덮개'로 혼용하여 사용했습니다.
    *실제로 실행해보면 답이 나오지 않고 모두 IMP값으로 출력됩니다.

    #include<iostream>
    #include<vector>
    #include<cmath>
    #include<algorithm>
    
    #define PI 3.1415926
    //전체 영역을 커버하는 것이 불가능 할 경우 IMP를 리턴합니다.
    #define IMP 200000000
    
    using namespace std;
    
    //초소의 위치 정보와 감시영역을 저장하는 클래스 입니다.
    class GuardPoint{
        private:
            double y,x,r;
        public:
            GuardPoint(){}
            GuardPoint(double ypos,double xpos,double radix)
            :y(ypos),x(xpos),r(radix){}
            double& GetY(void){return y;}
            double& GetX(void){return x;}
            double& GetR(void){return r;}
    };
    
    //구간을 시작점 오름차순으로 정렬 할 때 쓰일 비교함수 입니다.
    class COMPARE{
        public:
            bool operator()(const pair<double,double>& r1,const pair<double,double>& r2){
                return r1.first<r2.first;
            }
    };
    
    //N개의 초소를 의미합니다.
    int N;
    //변수 입력에 쓰일 임시 변수 입니다.
    double T1,T2,T3;
    //초소를 저장할 벡터입니다.
    vector< GuardPoint > GP;
    //초소를 구간 범위 pair로 저장할 벡터입니다.
    vector< pair<double,double> > I;
    
    //간단한 max함수 입니다.
    template<typename T>
    T bigger(const T r1,const T r2){return (r1>r2)? r1:r2;}
    //간단한 min함수 입니다.
    template<typename T>
    T smaller(const T r1,const T r2){return (r1<r2)? r1:r2;}
    
    //초소의 정보를 구간정보로 변환 시켜주는 함수 입니다.
    //atan 대신 asin을 사용하였습니다.
    //loc은 항상 [0,2pi]를 만족하게 구해지고,range는 [0,pi]를 만족하게 구해집니다.
    void mk_interval(void){
        double loc,range;
        for(int i=0;i<GP.size();i++){
            //loc가 1사분면의 각인 경우.
            if(GP[i].GetX()>0&&GP[i].GetY()>=0){
                loc=asin(GP[i].GetY()/8);
            }
            //loc가 2사분면의 각인 경우.
            else if(GP[i].GetX()<=0&&GP[i].GetY()>0){
                loc=PI-asin(GP[i].GetY()/8);
            }
            //loc가 3사분면의 각인 경우.
            else if(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에 속하는 지를 반환합니다.
    bool is_include(const double po,const pair<double,double>& iv){
        bool ret=false;
        for(int i=0;i<2;i++){if(iv.first<=po+2*PI*i&&po+2*PI*i<iv.second){ret=true;break;}}
        return ret;
    }
    
    //덮개들이 있을 때, 직선을 덮는 문제라고 생각하여 답을 내는 함수 입니다.
    //직선의 시작점과 종료점이 주어집니다.
    int mk_linear(double sp,double ep){
        int ret=0,idx=0;
        double biggest;
        //직선이 남아 있을때 까지 반복합니다.
        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){return IMP;}
            //위의 논리에 맞게 sp를 수정해줍니다.
            sp=biggest;
            //하나를 사용했으니 리턴값도 1 증가 합니다.
            ret++;
        }
        return ret;
    }
    
    //답을 반환하는 함수입니다.
    int mk_answer(void){
        int temp,ret=IMP;
        //모든 저장된 덮개(구간)들을 순회하면서, 아래를 실행합니다.
        for(int i=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);
        }}
        return ret;
    }
    
    int main(void){
        int TC;
        cin>>TC;
        while(TC--){
            GP.clear();
            I.clear();
            //입력을 받습니다.
            cin>>N;
            for(int i=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;
        }
        return 0;
    }
    

    꽤 오랜시간 여러번 확인해보았는데 어디서 틀렸는지 찾기가 힘이 듭니다 ㅠㅠ.
    개인적인 생각에
    1. asin계산 과정에서의 오차
    2. 원을 직선으로 피는 과정에서의 범위 계산 실수
    3. 책 p394
    "이때는 두 구간의 중심 ~~~ 증명할 수 있습니다."
    를 이해하지 못함.
    셋 중하나인 것 같은데, 딱히 답을 찾지 못했습니다.

    답변 기다립니다.

    좋은 하루, 좋은 연말, 좋은 새해 되세요!


    10년 전
6개의 댓글이 있습니다.
  • canuyes
    canuyes

    canuyes ㅠㅠ 답글이 달리지 않네요.
    어느부분을 좀 더 고쳐서 질문하면 될까요?


    10년 전 link
  • Being
    Being

    mk_linear 함수에서 idx 루프가 제대로 설정되지 않은 것 같습니다. 루프 한 차례만 돌고 나면 영원히 돌지 않겠네요.


    10년 전 link
  • Being
    Being

    이렇게 작은 예제에 대해서도 실패하는 경우, 그 예제를 손으로 풀어 계산 중간 과정을 로그로 찍어낸 것과 비교하면 추적하기 좋습니다.


    10년 전 link
  • canuyes
    canuyes

    감사합니다. 해결 되엇습니다.
    사실 atan과 atan2의 차이를 잘 이해할 수 없어서
    꼭 asin으로 풀어보고 싶었는데, 덕분에 풀었습니다.^^


    10년 전 link
  • Being
    Being

    부연하여 설명드리자면, atan()은 단일 변수로 \frac{y}{x}를 받습니다. 이는 수학적인 정의에 그대로 부합하지만, 실제 각도를 계산하는 용으로 써먹기 위해서는 이를테면 y > 0, x > 0 인 경우와 y < 0, x < 0인 경우를 구분해야 합니다. 그러려면 부호를 보고 atan()의 결과를 적당히 조작해야 하는데, 이 과정이 귀찮은데다가 고려해야 할 사항도 많아 틀리기 쉬우므로 대신 atan2()를 정의하여 yx를 모두 받도록 한 것입니다.


    10년 전 link
  • canuyes
    canuyes

    답변 감사합니다.
    수학에서 arctan의 치역이 [-pi/2,pi/2]인데
    왜 atan2는 치역이 [-pi,pi]가 되는지가 궁금했었는데,
    이제 알게 되네요 ^^
    행복한 새해되세요


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