Graham's Scan

Graham's Scan은 주어진 점 집합들의 Convex Hull을 $O(NlogN)$에 구하는 알고리즘이다.

 

1. Convex Hull에 무조건 포함되는 한 점 S를 잡는다. 일반적으로 x좌표가 최소인 점, 만약 여러개 있다면 y좌표가 최소인 점으로 잡는다.

2. S를 기준으로 전체 점들을 각도 순으로 정렬한다. 만약 S, p, q가 일직선 위에 있다면 S와의 거리 순으로 정렬한다.

3. 정렬한 순서대로 점들을 하나씩 보며, 스택에 점들을 하나씩 추가한다. 단, 스택의 점들은 들어가 있는 순서대로 시계 반대 방향으로, 즉 ccw가 양수로 유지되어야 한다. 이 불변식을 만족할 수 있도록 적절히 스택에서 점들을 제거해준 후, 새로운 점을 추가해준다.

 

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

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

const int MAXN = 1e5;
const ll INF = 1e18;

struct Point
{
	ll x, y;
};

Point operator + (Point p, Point q) { return {p.x+q.x, p.y+q.y}; }
Point operator - (Point p, Point q) { return {p.x-q.x, p.y-q.y}; }

ll ccw(Point p, Point q) { return p.x*q.y-p.y*q.x; }
ll ccw(Point p, Point q1, Point q2) { return ccw(q1-p, q2-p); }

ll norm(Point p) { return p.x*p.x+p.y*p.y; }
ll dist(Point p, Point q) { return norm(p-q); }

int N;
Point A[MAXN+10], S={INF, INF};

int main()
{
	scanf("%d", &N);
	for(int i=1; i<=N; i++) scanf("%lld%lld", &A[i].x, &A[i].y);

	for(int i=1; i<=N; i++)
	{
		if(S.x>A[i].x || (S.x==A[i].x && S.y>A[i].y)) S=A[i];
	}

	sort(A+1, A+N+1, [&](const Point &p, const Point &q)
	{
		if(ccw(S, p, q)!=0) return ccw(S, p, q)>0;
		return dist(S, p)<dist(S, q);
	});

	vector<Point> S;
	for(int i=1; i<=N; i++)
	{
		while(S.size()>1 && ccw(S[S.size()-2], S[S.size()-1], A[i])<=0) S.pop_back();
		S.push_back(A[i]);
	}

	printf("%d\n", S.size());
}