백준 7420번: 맹독 방벽 (C++)

접근

https://www.acmicpc.net/problem/7420

7420번: 맹독 방벽

백준 1708번 볼록껍질에서 사용한 컨벡스헐 알고리즘을 이용하면 매우 쉽게 풀 수 있다.

https://ca.ramel.be/245

백준 1708번 : 볼록 껍질 (C++)

문제의 조건을 보면 맹독 방벽을 '가장 짧게' 설치하는 조건이 있다. 이때 도시들을 컨벡스헐로 탐색하여 최외곽 도시들을 연결하는 볼록다각형을 구한다. 만약 오목한 부분이 있다면 그것은 오목한 부분을 직선으로 잇는 볼록다각형보다 돌아가는, 즉 가장 짧다는 조건에 위배되기 때문에 무조건 가장 외곽을 지나는 볼록다각형을 따라 맹독 방벽을 건설해야 한다. 그리고 맹독 방벽의 꼭지점 부분의 둥근 부분을 모두 합하면 한개의 원주가 되기 때문에 2 * pi * r 즉 원의 외경 공식을 한번 더해주면 답을 구할 수 있다. 아래의 그림을 본다면 쉽게 이해할 수 있다.

위의 그림에서 내부 오각형이 컨벡스헐이고 문제에서 주어진 L 만큼 평행이동한다면, 컨벡스헐 도형의 꼭짓점 사이의 거리의 합이 맹독 장벽의 거리 계산에 이용될 수 있다. 그리고 그림에서 원주의 각도 a ~ e의 합은 항상 360도이다. 이는 어떤 도형이던지 볼록 다각형일 경우 성립한다.

즉 컨벡스헐 볼록 다각형의 변의 길이의 합 + 반지름이 L 인 원의 외경의 합을 정수 단위에서 반올림해준다면 답을 구할 수 있다.

코드

#include <math.h>

#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>

using namespace std;

#define _USE_MATH_DEFINES
#define endl '\n'
#define MAX_N 1001

struct INFO {
    long long x;
    long long y;
};

int N, L;
vector<INFO> Info;
vector<INFO> s;
vector<INFO> Vertex;

int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

long double Dist(INFO a, INFO b) {
    return sqrt((b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y));
}

long long ccw(INFO a, INFO b, INFO c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

bool cmp(INFO a, INFO b) {
    if (a.y == b.y) {
        return a.x < b.x;
    } else {
        return a.y < b.y;
    }
}

bool cmpccw(INFO a, INFO b) {
    long long res = ccw(Info[0], a, b);
    if (res) {
        return res > 0;
    } else if (a.y == b.y) {
        return a.x < b.x;
    } else {
        return a.y < b.y;
    }
}

int main(int argc, char** argv) {
    // freopen 주석 처리
    freopen("input.txt", "r", stdin);

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N >> L;
    int a, b;
    for (int i = 0; i < N; i++) {
        cin >> a >> b;
        Info.push_back({a, b});
    }

    // 컨벡스헐 알고리즘 적용하여 볼록다각형을 이루는 도시들의 좌표 s 에 저장
    sort(Info.begin(), Info.end(), cmp);
    sort(Info.begin() + 1, Info.end(), cmpccw);
    INFO tmp1, tmp2;
    for (int i = 0; i < N; i++) {
        while (s.size() >= 2) {
            tmp2 = s.back();
            s.pop_back();
            tmp1 = s.back();
            if (ccw(tmp1, tmp2, Info[i]) > 0) {
                s.push_back(tmp2);
                break;
            }
        }
        s.push_back(Info[i]);
    }

    // 컨벡스헐을 이루는 도시들 사이의 거리 합
    long double ans = 0;
    for (int i = 0; i < s.size(); i++) {
        ans += Dist(s[i], s[(i + 1) % s.size()]);
    }
    // 반지름이 L 인 원의 외경
    long double circle = M_PI * L * 2;

    cout << round(ans + circle) << endl;

    return 0;
}

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!