algospot FOSSIL

algospot : https://algospot.com/judge/problem/read/FOSSIL

github : https://github.com/junho0956/Algorithm/blob/master/algospot%20FOSSIL/algospot%20FOSSIL/%EC%86%8C%EC%8A%A4.cpp

 

 

algospot FOSSIL 문제입니다. 

삼분탐색을 통해서 해결한 문제이고 기하문제를 처음풀어보는거라서

개념다잡는데 시간이 좀 걸렸습니다.

 

#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;
}