[C++] 21624번 Fence

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

---

 

25/12/28

 

 

7420번과 거리 기준만 달라진 문제이다.

---

 

문제 접근 방식:

 

 

울타리와 집 사이의 맨하탄 거리($L_{1}$ norm)가 적어도 $l$이 되도록 울타리를 둘러쌀 때, 울타리의 최소 둘레를 구하는 문제이다.

만약 맨하탄 거리가 아니라 우리가 잘 아는 유클리디안 거리($L_{2}$ norm)라면 7420번 맹독 방벽 문제와 동일하다.

그리고 그 문제의 풀이는, 기존 볼록 껍질의 둘레 + 반지름이 $l$인 원의 둘레와 같았다.(볼록껍질의 꼭짓점마다 부채꼴이 붙는다고 생각하자.)

이 문제도 사실 거리 기준만 $L_{1}$으로 달라졌다 뿐이지 본질적으로 똑같은 문제이다.

$L_{1}$에서의 원의 둘레는 $4\sqrt{ 2 }l$이다.

따라서, 볼록껍질의 둘레 + $4\sqrt{ 2 }l$이 정답이 된다.

---

아래는 내가 위의 접근 방식과 같이 작성한 C++ 코드이다. 더보기를 누르면 확인할 수 있다.

// 21624번 Fence
// 볼록껍질
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>

using namespace std;
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'

struct Point{
    long long x, y;
    Point() : x(0), y(0) {};
    Point(long long x, long long y) : x(x), y(y) {};    
    Point operator+(const Point& p) const {return {x+p.x, y+p.y};}
    Point operator-(const Point& p) const {return {x-p.x, y-p.y};}
    bool operator<(const Point& p) const {
        if (x == p.x) return y < p.y;
        return x < p.x;
    }
    bool operator==(const Point& p) const {
        return (x==p.x) && (y==p.y);
    }
};

long long cross(const Point& p1, const Point& p2){
    return p1.x*p2.y - p2.x*p1.y;
}

int ccw(const Point& p1, const Point& p2, const Point& p3){
    Point p = p2-p1, q = p3-p2;
    long long val = cross(p, q);
    if (val > 0) return 1; // 반시계
    if (val == 0) return 0; // 일직선
    if (val < 0) return -1; // 시계
}

// ConvexHull with monotone chain(Three Point non-colinear)
std::vector<Point> convexHull(std::vector<Point> points){
    std::vector<Point> hull;
    if (points.size() < 3) return hull;
    sort(points.begin(), points.end());
    std::vector<Point> lowerHull, upperHull;
    for (int i = 0; i < points.size(); ++i){
        if (lowerHull.size() < 2){
            lowerHull.push_back(points[i]);
        } else {
            while((lowerHull.size() >= 2) && (ccw(lowerHull[lowerHull.size()-2], lowerHull[lowerHull.size()-1], points[i]) <= 0)){
                lowerHull.pop_back();
            }
            lowerHull.push_back(points[i]);
        }
    }
    for (int i = 0; i < lowerHull.size(); ++i) hull.push_back(lowerHull[i]);
    for (int i = 0; i < points.size(); ++i){
        if (upperHull.size() < 2){
            upperHull.push_back(points[i]);
        } else {
            while((upperHull.size() >= 2) && (ccw(upperHull[upperHull.size()-2], upperHull[upperHull.size()-1], points[i]) >= 0)){
                upperHull.pop_back();
            }
            upperHull.push_back(points[i]);
        }
    }
    if (upperHull.size() > 2){
        for (int i = upperHull.size()-1; i > 0; --i){
            hull.push_back(upperHull[i]);
        }
    }
    if (hull.size() < 3) return std::vector<Point> ();
    return hull;
}

double distance(const Point& a, const Point& b){
    return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}

int main(void){
    fastio

    int N, L; cin >> N >> L;
    vector<Point> points(N);
    for (int i = 0; i < N; ++i){
        cin >> points[i].x >> points[i].y;
    }
    vector<Point> hull = convexHull(points);
    double ans = 4*sqrt(2)*L;
    for (int i = 0; i < hull.size(); ++i){
        ans += distance(hull[i], hull[(i+1)%hull.size()]); 
    }
    cout << fixed << setprecision(10);
    cout << ans;

    return 0;
}