10254번: 고속도로 - 컨벡스 헐(캘리퍼스)

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

10254번: 고속도로

 

참고 링크

https://anz1217.tistory.com/106

컨벡스 헐

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

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

int N;
pll point[200000];

ll dist(pll p1, pll p2)
{
    return (p1.first - p2.first) * (p1.first - p2.first)
        + (p1.second - p2.second) * (p1.second - p2.second);
}

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

    if (val > 0) return 1; //시계 방향
    else if (val < 0) return -1; //반시계 방향
    else return 0; //일직선
}

pll vec(pll p1, pll p2) //두 점의 벡터
{
    return { p2.first - p1.first, p2.second - p1.second };
}

bool compare(pll a, pll b) //반시계 방향 순으로 정렬
{
    pll va = vec(point[0], a);
    pll vb = vec(point[0], b);

    int val = ccw(va, vb);
    if (val == 1) return true;
    else if (val == -1) return false;
    else
    {
        if (dist(point[0], a) < dist(point[0], b)) return true;
        else return false;
    } //ccw가 같다면 길이가 더 짧은 순으로 정렬
}

void solve()
{
    cin >> N;
    for (int i{ 0 }; i < N; i++)
    {
        cin >> point[i].first >> point[i].second;
        if (point[i] < point[0]) swap(point[0], point[i]);
    } /* 맨 처음 좌표는 x좌표가 가장 작은 점이며,
      그런 점이 여러 개라면 y좌표가 가장 작은 점이다. */

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

    vector<pll> ch; //컨벡스 헐의 좌표
    for (int i{ 0 }; i < N; i++)
    {
        while (ch.size() > 1) //최소 2개의 좌표는 있어야 한다.
        {
            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);

            int val = ccw(v1, v2);
            if (val > 0) break;
            //컨벡스 헐의 세 좌표를 임의로 고르면 무조건 반시계 방향이다.

            ch.pop_back();
        }
        ch.push_back(point[i]);
    }

    int i1 = min_element(ch.begin(), ch.end()) - ch.begin(); //x좌표가 가장 작은 좌표
    int i2 = max_element(ch.begin(), ch.end()) - ch.begin(); //x좌표가 가장 큰 좌표

    ll mxDist{ 0 };
    int ans1{ -1 }, ans2{ -1 };

    for (int i{ 0 }; i < ch.size(); i++)
    {
        pll p1 = ch[i1], p1_next = ch[(i1 + 1) % ch.size()];
        pll p2 = ch[i2], p2_next = ch[(i2 + 1) % ch.size()];
        //현재 좌표와 다음 좌표

        ll curDist = dist(p1, p2);
        if (curDist > mxDist)
        {
            mxDist = curDist;
            ans1 = i1, ans2 = i2;
        } //길이 갱신

        pll v1 = vec(p1, p1_next);
        pll v2 = vec(p2_next, p2);
        //캘리퍼스를 p2_next에 옮겨보면 엇각의 성질로 ccw를 통한 각도 비교 가능

        if (ccw(v1, v2) > 0) i1 = (i1 + 1) % ch.size();
        else i2 = (i2 + 1) % ch.size();
        //각도가 작은 쪽으로 캘리퍼스 회전
    }
    cout << ch[ans1].first << " " << ch[ans1].second << " "
        << ch[ans2].first << " " << ch[ans2].second << "\n";
}

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

    int T; cin >> T;
    for (int i{ 1 }; i <= T; i++) solve();
}