세울큰학원(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;
}

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

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


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

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


    9년 전 link
  • restart
    restart

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


    9년 전 link

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