FOSSIL 문제의 코드부분에 궁금증이 있습니다.

  • junnnho
    junnnho

    궁금한 부분은 이 부분입니다.
    double lo = max(minX(a), minX(b));
    double hi = min(maxX(a), maxX(b));

    solve 함수 내에서 삼분탐색을 위해 가장 초기값을 잡는 부분이 위의 두 코드인데
    문제의 목적은 다각형의 교차부분에 대한 길이를 찾는 것이니
    교차하는 다각형에 대한 끝점들을 초기값으로 잡아야되는 것이 아닌가 하는 궁금증 입니다.

    저 두 코드로 초기값을 잡게되면 교차점의 끝점보다 더 왼쪽이나 오른쪽에 있는 x좌표가 초기값으로 잡힐 수 있고,
    이렇게 되면 삼분탐색 과정간에서 교차하는 부분을 탐색하게 될 수도 있지만 교차안하는 부분을 탐색할 수도 있는 것 아닌가 싶어서 질문드립니다.

    이에 대해 제가 생각해본 부분은
    교차 안하는 부분을 탐색하게 되면 vertical 함수로 구해지는 길이가 음수로 반환이 되니 더 큰 값을 찾아 삼분탐색을 하게되면서 자연스럽게 교차하는 부분을 찾아가게되니 문제없는 것 같기도 하고..

    제 생각한 부분이 얼추 맞는건지 아니면 저렇게 사용하는 정확한 이유가 궁금합니다.

    질문을 위해서 아래에 코드를 첨부해놓겠습니다.

    #include <iostream>
    #include <vector>
    #include <queue>
    #include <stack>
    #include <algorithm>
    #include <set>
    #include <cmath>
    #include <limits>
    using namespace std;
    
    struct point {
        double x, y;
    };
    typedef vector<pair<point, point> > vp;
    
    void decompose(vp & upper, vp& lower, vector<point>& a) {
        int n = a.size();
        for (int i = 0; i < n; i++) {
            if (a[i].x < a[(i + 1) % n].x) {
                lower.push_back({ a[i], a[(i + 1) % n] });
            }
            else {
                upper.push_back({ a[i], a[(i + 1) % n] });
            }
        }
    }
    
    double minX(vector<point>& a) {
        double ans = 1e9;
        for (int i = 0; i < a.size(); i++) {
            ans = min(ans, a[i].x);
        }
        return ans;
    }
    
    double maxX(vector<point>& a) {
        double ans = -1;
        for (int i = 0; i < a.size(); i++) {
            ans = max(ans, a[i].x);
        }
        return ans;
    }
    
    bool between(pair<point,point>& line, double x) {
        return (line.first.x <= x && x <= line.second.x) || (line.second.x <= x && x <= line.first.x);
    }
    
    double calY(point& a, point& b, double x) {
        // 직선의 방정식
        // y = m(x-x1)+y1
        return (b.y - a.y) / (b.x - a.x) * (x - a.x) + a.y;
    }
    
    // 주어진 x좌표에 대해서 껍질들의 y좌표를 확인하여 그 차액(길이)를 리턴한다.
    double len(vp& upper, vp& lower, double x) {
        double minY, maxY;
        minY = 1e9, maxY = -1;
        // 위껍질의 선분들을 확인하여 주어진 x와 겹치는 y의 최솟값을 찾는다
        for (int i = 0; i < upper.size(); i++) {
            // 위껍질의 선분이 현재 x점의 수직선과 마주치는지 확인한다
            if (between(upper[i], x)) {
                // 만약 마주친다면(겹쳐진다면) 직선의 방정식 공식을 이용하여 x에 대한 y점을 가져온다.
                minY = min(minY, calY(upper[i].first, upper[i].second, x));
            }
        }
    
        // 아래껍질의 선분들을 확인하여 주어진 x와 겹치는 y의 최댓값을 찾는다
        for (int i = 0; i < lower.size(); i++) {
            // 위껍질의 선분이 현재 x점의 수직선과 마주치는지 확인한다
            if (between(lower[i], x)) {
                // 만약 마주친다면(겹쳐진다면) 직선의 방정식 공식을 이용하여 x에 대한 y점을 가져온다.
                maxY = max(maxY, calY(lower[i].first, lower[i].second, x));
            }
        }
    
        // 길이를 반환한다
        return minY - maxY;
    }
    
    double solve(vp& upper, vp& lower, vector<point>& a, vector<point>& b) {
        double lo = max(minX(a), minX(b));
        double hi = min(maxX(a), maxX(b));
        // 겹치지 않는 경우
        if (hi < lo) return 0;
    
        for (int i = 0; i < 100; i++) {
            double lp = (2 * lo + hi) / 3;
            double rp = (lo + 2 * hi) / 3;
            if (len(upper, lower, lp) < len(upper, lower, rp))
                lo = lp;
            else
                hi = rp;
        }
    
        // 경우에 따라 교집합의 길이가 아닌 부분이 반환될 수 있으니 (음수) 조건을 주어서 반환한다
        return max(0.0, len(upper, lower, hi));
    }
    
    int main() {
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
        int T; cin >> T;
        while (T--) {
            int n, m;
            cin >> n >> m;
    
            vector<point> poly1, poly2;
    
            for (int i = 0; i < n; i++) {
                point a;
                cin >> a.x >> a.y;
                poly1.push_back(a);
            }
            for (int i = 0; i < m; i++) {
                point a;
                cin >> a.x >> a.y;
                poly2.push_back(a);
            }
    
            // 아래, 위 껍질을 구분해준다
            // 껍질의 구분으로 받게 될 값들은 "선분" 이 기준이 된다
            vp upper, lower;
    
            decompose(upper, lower, poly1);
            decompose(upper, lower, poly2);
    
            // 껍질을 구분했으면 삼분탐색을 통해 문제를 해결한다
            cout << fixed;
            cout.precision(10);
            cout << solve(upper, lower, poly1, poly2) << "\n";
        }
    
        return 0;
    }
    

    7달 전
1개의 댓글이 있습니다.
  • junnnho
    junnnho

    아.. 바로 뒷부분에 이에 대한 설명이 있었네요 ㅠㅠ
    공부 똑바로 하고 질문올리겠습니다!


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