[종만북] 문제: FOSSIL

문제

다각형 A와 다각형 B가 주어질 때 이의 교집합의 y좌표 폭의 최댓값을 구하는 문제입니다.

문제 링크

---

서론

다각형의 교집합을 구하는 방법과 교집합의 y좌표의 폭은 유니모달 함수로 표현할 수 있으므로, 최댓값을 삼분 탐색을 통해 구해봅시다.

---

알고리즘 구상

아이디어

최댓값은 고사하고 다각형의 교집합도 못 구하게 생겼습니다..

일단, 이 문제는 굳이 교집합을 구해야 하는 문제는 아닙니다.

교집합을 구하려면 그래픽스 알고리즘(Sutherland-Hodgman 등)을 쓰고… 해야 합니다.

대신, 교집합의 y좌표의 폭의 최댓값을 구하기만 하면 되는 문제입니다.

다각형의 정점들이 주어지는데, 이 정점 간에 선분은 일차함수 입니다.

다각형에 속한다는 것은 이 일차함수의 위 혹은 아래에 위치한다는 것인데, 이를 어떻게 구별할 수 있을까요?

문제에서도 다행히(!) 시계 반대 방향으로 정렬해서 정점의 좌표를 줍니다.

정점의 좌표가 정렬되있다 하였으니, x의 변화량이 양수 $=$ $\Delta x > 0(\Delta x = x_{i+1}-x_i)$이면, 이때의 선분(일차함수)의 윗부분이 다각형.. 다각형의 아랫부분임을 의미합니다.

$\Delta x < 0$이면, 다각형의 윗부분이고요.

이렇게 다각형의 아랫부분과 윗부분을 나눠보면, 아랫부분은 아래로 볼록함수임을 알 수 있고, 윗 부분은 위로 볼록함수임을 알 수 있습니다.

다각형 2개가 주어지므로, 위로 볼록함수 2개와 아래로 볼록함수 2개가 주어집니다.

y좌표가 더 높은 아래로 볼록 함수를 $f(x)$, y좌표가 더 낮은 위로 블록 함수를 $g(x)$라 하면 문제는 $g(x) - f(x)$의 최댓값을 구하는 문제로 바꿀 수 있습니다.

$g(x) - f(x)$는 결국 유니모달 함수처럼 하나의 극대를 가지기 때문에, 삼분 탐색을 활용하여 값을 찾을 수 있습니다!

알고리즘 설계

1. 다각형의 각 $edge$들에 대해 $lower$인지, $upper$인지 파악합니다. 이때, 수직선의 경우는 포함하지 않습니다. (상관없는 문제입니다.)
2. $upper$의 각 선분에 대해 $x$값이 주어지면, $g(x) = \min_{x \in upper} y$를 구합니다.
3. $lower$에 대해서도 똑같이 하나, $max$값을 구합니다. $f(x) = \max_{x \in lower} y$
4. $\max(g(x) - f(x))$를 삼분탐색으로 구합니다.

---

알고리즘 구현

사용할 STL들

선분을 보관하려면 적어도 두개의 정점을 저장해야합니다.

따라서 vector<pair<double, double>>을 이용합니다.

전처리함수

다각형의 $edge$를 아랫부분lower이랑 윗부분upper으로 나누는 함수입니다.

이후 삼분탐색의 범위를 설정하기 위해 다각형의 최대/최소 $x$좌표를 미리 구해놓습니다.

void initData() {
    for (int i = 0; i < n; i++) {
        if (block1[i].x < block1[(i + 1) % n].x)
            lower.push_back(make_pair(block1[i], block1[(i + 1) % n]));
        else if (block1[i].x > block1[(i + 1) % n].x)
            upper.push_back(make_pair(block1[i], block1[(i + 1) % n]));
    }
    for (int i = 0; i < m; i++) {
        if (block2[i].x < block2[(i + 1) % m].x)
            lower.push_back(make_pair(block2[i], block2[(i + 1) % m]));
        else if (block2[i].x > block2[(i + 1) % m].x)
            upper.push_back(make_pair(block2[i], block2[(i + 1) % m]));
    }

    block1MinX = block1MaxX = block1[0].x;
    for (int i = 1; i < n; i++) {
        block1MinX = min(block1MinX, block1[i].x);
        block1MaxX = max(block1MaxX, block1[i].x);
    }

    block2MinX = block2MaxX = block2[0].x;
    for (int i = 1; i < m; i++) {
        block2MinX = min(block2MinX, block2[i].x);
        block2MaxX = max(block2MaxX, block2[i].x);
    }
}

유틸리티 함수

$x$가 선분 사이에 있는 $x$인지 판단하는 $between(x)$,

정점 2개와 $x$값이 주어지면 $f(x)$를 구하는 함수 $function(x)$입니다.

// coordinate의 x좌표 사이에 존재하는지 구하는 함수
bool between(const coord &a, const coord &b, double x) {
    return (a.x <= x && x <= b.x) || (b.x <= x && x <= a.x);
}

// 두 정점을 잇는 f(x)와 x좌표가 주어지면 f(x)를 구하는 함수
double function(const coord &a, const coord &b, double x) {
    return a.y + (b.y - a.y) * (x - a.x) / (b.x - a.x);
}

gap()

$g(x) - f(x)$를 구하는 함수 $gap(x)$입니다.

double gap(double x) {
    double minUp = 1e5, maxLow = -1e5;
    for (int i = 0; i < upper.size(); i++) {
        if (between(upper[i].first, upper[i].second, x))
            minUp = min(minUp, function(upper[i].first, upper[i].second, x));
    }
    for (int i = 0; i < lower.size(); i++) {
        if (between(lower[i].first, lower[i].second, x))
            maxLow = max(maxLow, function(lower[i].first, lower[i].second, x));
    }
    return minUp - maxLow;
}

optimize()

$gap()$를 통해 삼분탐색으로 값을 구하는 함수입니다.

double optimize() {
    double lo = max(block1MinX, block2MinX), hi = min(block1MaxX, block2MaxX);
    if (hi < lo) return 0.0;
    int it = 100;

    while (it--) {
        double aab = (lo * 2 + hi) / 3.0;
        double abb = (lo + hi * 2) / 3.0;
        double gapA = gap(aab);
        double gapB = gap(abb);
        if (gapA < gapB)
            lo = aab;
        else
            hi = abb;
    }

    return max(0.0, gap(hi));
}

최종 코드

여기에서 확인하세요!