백준 1708번 - 볼록 껍질

 

* 문제 링크

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

1708번: 볼록 껍질

 

 

 

문제 내용 요약

 

다각형의 아무 두 점을 잡아 선분을 그었을 때, 항상 다각형 내부에 존재하면 그 다각형을 볼록 다각형이라 한다.

 

2차원 평면에 N ( 3 ≤ N ≤ 100,000 ) 개의 점 중에 선택해서

 

모든 점들이 내부에 있도록 볼록 다각형을 만들었을 때 (Convex Hull) 의 선택한 점의 개수를 구해라.

 

 

 

 

 

CCW (Counter Clockwise)

 

세 점의 방향성을 시계/반시계 방향으로 알아내는 방법이다.

 

이것과 관련해서 따로 글을 쓰는 것이 좋을 것 같지만, 일단은 여기에 비교적 간단히 작성해보려 한다.

 

CCW는 보통 a, b, c 세 점에 대해서, a→b 방향의 벡터와 a→c 방향의 벡터의 방향을 의미한다.

 

 

CCW 구하는 식

 

 

 

CCW는 다음과 같이 구하며,

 

CCW > 0 일 때 반시계방향,
CCW < 0 일 때 시계방향,
CCW = 0 일 때 일직선 상에 존재함을 의미한다.

 

어디서 많이 본 느낌이다.

 

 

https://syerco0.tistory.com/9

다수의 점들을 각도에 따라 정렬하기

 

 

내가 썼던 전 글을 참고해보면,

 

기준점을 원점이 아닌 a = (a_x, a_y) 로 잡고 (평행이동),

 

u를 b, v를 c 점으로 놓으면 식이 일치한다.

 

이 CCW 또한 벡터곱을 이용한 것이라는 것을 알 수 있다.

 

 

 

이미 설명이 다 끝난 것 같지만, 추후에 CCW에 관한 글을 따로 작성할 수도 있을 것 같다.

 

많이 쓰기 때문에

 

 

 

 

컨벡스 헐 (Convex Hull) 알고리즘 (Graham's Scan)

 

링크로 올린 전 글에서 각도에 따른 정렬, 그리고 위의 CCW를 기반으로 한다.

 

설명은 백준에 나온 예시 입력을 기반으로 하겠다.

 

또한 사람들마다 약간씩 풀이가 다를 수 있으며, 나는 내가 짠 코드를 기준으로 설명하겠다.

 

예시 입력 (점 대충 찍음)

 

먼저, 주어진 점들 중에 가장 왼쪽 아래 (y좌표가 가장 작은, 같을 경우 x좌표가 가장 작은) 점을 기준으로

 

각도에 따라 반시계방향으로 정렬한다. (0번 점을 기준점으로 하고 1번 점부터 정렬된 형태로)

 

정렬하면 대충 이렇게 될 것이다

 

 

스택에 0번, 1번 점을 push하고 2번 점부터 Scan을 시작한다.

 

스택에서 가장 최근 2개의 점을 각각 a, b (a가 2번째로 나중에, b가 가장 나중에 스택에 넣은 점) ,
Scan할 점을 c라고 하였을 때

스택에 들어있는 점의 개수를 1개 이상으로 유지하면서
CCW ≤ 0 인 동안 pop,
CCW > 0 일 때 Scan한 점을 push 한다.

 

이 방법으로 Scan을 해주면 아래와 같이 진행된다.

 

CCW(0,1,2) = 0 1번 pop, 2번 push	CCW(0,2,3) > 0 3번 push	CCW(2,3,4) > 0 4번 push	CCW(3,4,5) < 0 4번 pop
CCW(2,3,5) > 0 5번 push	CCW(3,5,6) > 0 6번 push	CCW(5,6,7) < 0 6번 pop	CCW(3,5,7) > 0 7번 push

결과. 0과 7번은 자동으로 이어진다.

 

이렇게 Convex Hull 문제가 풀어진다.

 

Convex Hull을 이용한 최적화 문제도 있기 때문에

 

알고리즘 대회를 준비한다면 알아두는 것이 좋다고 생각한다. 빈도는 잘 모르겠다.

 

 

 

++ 2023.01.18 추가

 

까먹고 시간복잡도에 관한 이야기를 안 했다.

 

정렬 이후, 스택을 이용한 Convex Hull 구하기는 O(N) 의 시간복잡도를 가진다.

 

사실상 정렬, 보통 비교를 이용한 정렬의 경우 최소 O(NlogN) 의 시간복잡도를 가지므로

 

정렬에 의해 시간복잡도가 결정된다고 보면 된다.

 

 

 

내 코드

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
struct D{
	ll x,y;
};
bool cmp(D a,D b) {
	ll z=a.x*b.y-b.x*a.y;
	if(z==0) return abs(a.x)+abs(a.y)<abs(b.x)+abs(b.y);
	if(z>0) return 1;
	return 0;
}
bool ccw(D a,D b,D c) {
	ll z=(b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
	if(z>0) return 1;
	return 0;
}
D d[100010],crit={99999,99999},q[100010];
int main() {
	int n,t,s=2;
	cin>>n;
	for(int i=0;i<n;i++) {
		scanf("%lld %lld",&d[i].x,&d[i].y);
		if(d[i].y<crit.y||(d[i].y==crit.y&&d[i].x<crit.x)) crit={d[i].x,d[i].y},t=i;
	}
	swap(d[t],d[0]);
	for(int i=0;i<n;i++) {
		d[i].x-=crit.x;
		d[i].y-=crit.y;
	}
	sort(d+1,d+n,cmp);
	q[0]=d[0];
	q[1]=d[1];
	for(int i=2;i<n;i++) {
		while(s>1&&ccw(q[s-2],q[s-1],d[i])==0) s--;
		q[s++]=d[i];
	}
	cout<<s;
}

 

이번에도 귀찮아서 더 최적화하지는 않았다.