[알고리즘 정리] 그라함 알고리즘(Graham’s scan) 알고리즘

ccw 알고리즘(?)을 이용하여 블록 껍질(convex hull)을 뽑아내는 알고리즘 입니다.

CCW(Counter Clock Wise) 알고리즘

시간복잡도는 O(nlogn)

# 풀이 순서

1. 가장 x, y가 작은 ori점을 찾는다.

2. ori 이외의 점들을 반시계 방향을 정렬한다.

3. ccw를 활용하여 블록 껍질을 찾는다.

ccw>0이 되었을 때만 스택에 넣어주면 된다.

# 관련문제 : https://www.acmicpc.net/problem/1708

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#define MAX 200005
#define INF 987654321
#define MOD 31991
#pragma warning(disable:4996)
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;

struct st{
    int x,y;
    int p,q;
    st() : x(0),y(0),p(0),q(0){}
    st(int x1, int y1): x(x1),y(y1),p(0),q(0){}
}s[MAX];
// x, y : 원래 좌표 p, q : 기준점에 대한 좌표

bool cmp(const st &a,const st &b)
{
    if (1LL * a.q * b.p != 1LL * a.p*b.q)
        return 1LL * a.q * b.p < 1LL * a.p*b.q;
    // 기준점을 (0,0)이라 했을때 ccw라 생각하면 된다.
    if (a.y != b.y)
        return a.y < b.y;
    return a.x < b.x;
}
// a, b에 대한 좌표 정렬 하기 위한 함수

ll ccw(const st &a,const st &b,const st &c) {
    return 1LL * (a.x * (b.y-c.y) + b.x*(c.y-a.y) + c.x*(a.y-b.y));
}
// ccw 함수


int t,n;
vector<int> v;

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        s[i]=st(x,y);
    }
    sort(s,s+n,cmp);
    // 가장 작은 x,y(ori)를 가지는 좌표를 찾는다.
    
    for(int i=1;i<n;i++)
    {
        s[i].p=s[i].x-s[0].x;
        s[i].q=s[i].y-s[0].y;
    }
    sort(s+1,s+n,cmp);
    // ori를 기준으로 다른 좌표들을 반시계 방향으로 정렬한다.
    
    v.push_back(0);
    v.push_back(1);
    // 최초 2개의 점을 넣는다.
    
    int next = 2;
    // 다음 넣을 점
    while (next < n)
    // convex hull 만들기
    {
        while (v.size() >= 2)
        {
            int first, second;
            second = v.back();
            v.pop_back();
            first = v.back();
            if (ccw(s[first], s[second], s[next]) > 0)
            // 바로 이전 2개의 점과 새로운 다음 점이 반 시계방향이라면 넣는다.
            {
                v.push_back(second);
                break;
            }
        }
        v.push_back(next++);
        // 다음 점을 넣는다.
    }
    printf("%d",v.size());
    // 블록의 껍질 개수를 출력한다.
    return 0;
}