세울큰학원(SEOULGREUNIV) 왜 오답이 뜰까요ㅠㅠ?

  • restart
    restart

    문제설명

    N(<=8)개의 선분들이 주어지고, 각 선분 사이를 잇는 모든 선분을 그릴 때, 그 넓이를 구하는 문제입니다.

    알고리즘 구상

    1. 선분들에서 2개를 골라 사각형을 만든다. 선택된 선분이 AB,CD라 할 때, - 선분 AC와 BD가 교차하면 사각형은 ABCD - 교차하지 않으면 ABDC

    2. 각 사각형의 모든 변을 기준으로 하여 모든 교차점을 찾는다.
      교차점들의 x좌표를 set에 추가한다

    3. 2에서 만들어진 set의 인접요소들을 순회하면서 심슨법을 적용한다.
      delta X = (X_{i+1} - X_{i} ) / 2
      mid X = (X_{i+1} + X_{i} ) / 2
      로 삼으면, 각 사각형들을 순회하면서 선분 (mid X, 0) - (mid X, INF)와의 교차점을 찾는다. 교차점의 y좌표는 심슨법에서 y_2가 된다. 이 교차점은 항상 2개이거나 0개이므로 큰쪽을 사각형 영역의 시작으로 삼고, 작은 쪽을 끝으로 삼는다.
      교차점들을 y좌표가 큰순으로 순회하면서, 겹치는 사각형의 수를 세면서 칠해진 부분이 시작될 때 2 * delta X * y_2 를 더하고, 칠해진 부분이 끝날 때 2 * delta X * y_2 를 빼준다.

    코딩

    #include <cstdio>
    #include <set>
    #include <functional>
    #include <algorithm>
    #include <cmath>
    using namespace std;
    const double PI=2.0*acos(0.0);
    const double EPSILON=1e-9;
    const double INF=1e200;
    
    struct vector2{
        double x,y;
        explicit vector2(double x_=0.0, double y_=0.0) : x(x_), y(y_) {}
        bool operator==(const vector2& rhs){
            return (x==rhs.x) && (y==rhs.y);
        }
        bool operator<(const vector2& rhs){
            return (x==rhs.x)? y<rhs.y : x<rhs.x;
        }
        vector2 operator+(const vector2& rhs){
            return vector2(x+rhs.x, y+rhs.y);
        }
        vector2 operator-(const vector2& rhs){
            return vector2(x-rhs.x, y-rhs.y);
        }
        vector2 operator*(const double rhs){
            return vector2(x*rhs, y*rhs);
        }
        double norm() const { return hypot(x,y); }
    
        vector2 normalize() const{
            return vector2(x/norm(),y/norm());
        }
        double polar(){
            return fmod(atan2(y,x)+2*PI, 2*PI);
        }
        double dot(const vector2& rhs){
            return x*rhs.x+y*rhs.y;
        }
        double cross(const vector2& rhs){
            return x*rhs.y-y*rhs.x;
        }
        vector2 project(const vector2& rhs) const{
            vector2 r=rhs.normalize();
            return r*r.dot(*this);
        }
    
    };
    double ccw(vector2 a,vector2 b){
        return a.cross(b);
    }
    double ccw(vector2 p,vector2 a,vector2 b){
        return ccw(a-p,b-p);
    }
    bool lineIntersection(vector2 a,vector2 b,
                            vector2 c,vector2 d,vector2& x){
        //a+p(b-a)=b+q(d-c)
        double det=(b-a).cross(d-c);
        if(fabs(det)<EPSILON) return false;
        x=a+(b-a)*((c-a).cross(d-c)/det);
        return true;
    }
    bool parallelSegments(vector2 a,vector2 b,
                            vector2 c,vector2 d, vector2& p){
        if(b<a) swap(a,b);
        if(d<c) swap(c,d);
        if(ccw(a,b,c)!=0 || b<c || d<a) return false;
        if(a<c) p=c; else p=a;
        return true;
    }
    bool inBoundingRectangle(vector2 p, vector2 a, vector2 b){
        if(b<a) swap(a,b);
        return p==a || p==b || (a<p && p<b);
    }
    bool segmentIntersection(vector2 a, vector2 b,
                            vector2 c, vector2 d, vector2& p){
        if(!lineIntersection(a,b,c,d,p))
            return parallelSegments(a,b,c,d,p);
        return inBoundingRectangle(p,a,b) && inBoundingRectangle(p, c, d);
    }
    bool segmentIntersects(vector2 a,vector2 b,vector2 c,vector2 d){
        double ab=ccw(a,b,c)*ccw(a,b,d);
        double cd=ccw(c,d,a)*ccw(c,d,b);
        if(ab==0 && cd==0){
            if(b<a) swap(a,b);
            if(d<c) swap(c,d);
            return !(b<c || d<a);
        }
        return ab<=0 && cd<=0;
    }
    vector2 perpendicularFoot(vector2 p, vector2 a, vector2 b){
        return a+(p-a).project(b-a);
    }
    double pointToLine(vector2 p, vector2 a,vector2 b){
        return (p-perpendicularFoot(p,a,b)).norm();
    }
    
    typedef vector<vector2> polygon;
    vector< polygon > sqs;
    vector< pair <vector2, vector2> > segs;
    int T,N;
    
    int main() {
        scanf("%d",&T);
        while(T--){
            scanf("%d",&N); sqs.clear(); segs.clear();
            for(int i=0;i<N;i++){
                vector2 a,b;
                scanf("%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y);
                segs.push_back(make_pair(a,b));
            }
            for(int i=0;i<N;i++){
                for(int j=i+1;j<N;j++){
                    if(segmentIntersects(segs[i].first,segs[j].first,
                                         segs[i].second,segs[j].second))
                        swap(segs[j].first, segs[j].second);
                    segs.push_back(make_pair(segs[i].first,segs[j].first));
                    segs.push_back(make_pair(segs[i].second,segs[j].second));
                    polygon sq;
                    sq.push_back(segs[i].first);
                    sq.push_back(segs[i].second);
                    sq.push_back(segs[j].second);
                    sq.push_back(segs[j].first);
                    sqs.push_back(sq);
                }
            }
            set<double> xs;
            for(int i=0;i<segs.size();i++)
                for(int j=i+1;j<segs.size();j++){
                    vector2 p;
                    if(segmentIntersection(segs[i].first,segs[i].second,
                                            segs[j].first,segs[j].second,p))
                        xs.insert(p.x);                         
                }
            double last=-1, res=0.0;
            for(auto &i : xs){
                if(last<-0.5) { last=i; continue; }
                double deltax=(i-last)*0.5, midx=(i+last)*0.5;
                vector2 ma(midx,0.0), mb(midx,INF);
                vector< pair<double, int> > area;
                for(int j=0;j<sqs.size();j++){
                    double pl=0.0,mi=INF;
                    for(int k=0;k<4;k++){
                        int nxt=(k+1)%4; vector2 p;
                        if(segmentIntersection(sqs[j][k], sqs[j][nxt],
                                            ma, mb, p)){
                            pl=max(pl,p.y);
                            mi=min(mi,p.y);
                        }
                    }
                    if(pl>mi){
                        area.push_back(make_pair(pl,1));
                        area.push_back(make_pair(mi,2));
                    }
                }
                sort( area.begin(), area.end() , greater< pair<double, int> >());
                int cnt=0;
                for( auto &j : area ){
                    if(j.second==1){
                        cnt++;
                        if(cnt==1) res+=deltax*j.first*2.0;
                    }else{
                        cnt--;
                        if(cnt==0) res-=deltax*j.first*2.0;
                    }
                }
                last=i;
            }
            printf("%.12f\n",res);
        }
        return 0;
    }
    

    (알고리즘 문제 해결 전략의 기하라이브러리 사용)

    기하는 디버그가 너무 어려워요ㅜㅜ.......


    5년 전
2개의 댓글이 있습니다.
  • Taeyoon_Lee
    Taeyoon_Lee

    알고리즘 자체는 맞을 것 같은데요.. 저라면 이렇게 해볼 것 같습니다.
    1) 랜덤 데이터 제네레이터를 만든다.(눈으로 확인할 수 있는 쉬운 데이터만 나오는..)
    2) 몬테카를로로 풀어본다.
    3) 1, 2를 이용해서 오차가 심한 데이터를 찾는다.
    4) 찾은 데이터를 직접 그려보며 디버깅....:'(


    5년 전 link
  • restart
    restart

    알고리즘상 문제가 있었습니다ㅠ.ㅠ 두 직선간 영역이 무조건 사각형이 아니고, 삼각형일 경우와 면적이 0인 직선일 경우가 있었네요.. 이걸 예외처리하고 나니 AC가 됐습니다. 참 오래 걸렸네요ㅋㅋㅋㅋㅠㅠ


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