7420번: 맹독 방벽 - 컨벡스 헐

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

7420번: 맹독 방벽

 

1. 컨벡스 헐을 구한다.

2. 컨벡스 헐에 포함된 좌표들을 연결한 길이 + L을 반지름으로 하는 원주

외각의 합은 360도이기에 호가 포함된 영역의 길이의 합은 L을 반지름으로 하는 원주이다.

물론 내적의 성질을 이용해 arccos을 구해 호를 일일이 구해도 된다.

#define _SILENCE_ALL_CXX20_DEPRECATION_WARNINGS
#define pi 3.14159265358979
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int N, L;
pll point[1000];
vector<pll> CH;
double ans{ 0 };

ll dist(pll p1, pll p2)
{
    auto [x1, y1] = p1;
    auto [x2, y2] = p2;
    return (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1);
}

int ccw(pll v1, pll v2)
{
    ll res = v1.first * v2.second - v1.second * v2.first;

    if (res > 0) return 1;
    else if (res < 0) return -1;
    else return 0;
}

pll vec(pll p1, pll p2)
{
    return { p2.first - p1.first, p2.second - p1.second };
}

bool compare(pll p1, pll p2)
{
    pll v1 = vec(point[0], p1);
    pll v2 = vec(point[0], p2);

    int val = ccw(v1, v2);
    if (val == 1) return true;
    else if (val == -1) return false;
    else
    {
        if (dist(point[0], p1) < dist(point[0], p2)) return true;
        else return false;
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> N >> L;
    for (int i{ 0 }; i < N; i++)
    {
        cin >> point[i].first >> point[i].second;
        if (point[i] < point[0]) swap(point[0], point[i]);
    }

    sort(point + 1, point + N, compare);

    for (int i{ 0 }; i < N; i++)
    {
        while (CH.size() > 1)
        {
            pll p1 = CH[CH.size() - 2];
            pll p2 = CH[CH.size() - 1];
            pll p3 = point[i];

            pll v1 = vec(p1, p2);
            pll v2 = vec(p2, p3);

            if (ccw(v1, v2) == 1) break;
            CH.pop_back();
        }
        CH.push_back(point[i]);
    }

    if (CH.size() > 2)
    {
        for (int i{ 0 }; i < CH.size(); i++)
        {
            pll p1 = CH[i % CH.size()];
            pll p2 = CH[(i + 1) % CH.size()];

            pll v1 = vec(p2, p1);

            ans += sqrt(v1.first * v1.first + v1.second * v1.second);
        }
        ans += 2 * pi * L;
        cout << fixed << setprecision(0) << ans;
    }
    else if(CH.size() == 2)
    {
        cout << fixed << setprecision(0) <<
            sqrt(dist(CH[0], CH[1])) * 2 + 2 * pi * L;
    }
}