[컨벡스 헐 단계] 백준 1708번 볼록 껍질

문제

다각형의 임의의 두 꼭짓점을 연결하는 선분이 항상 다각형 내부에 존재하는 다각형을 볼록 다각형이라고 한다. 아래 그림에서 (a)는 볼록 다각형이며, (b)는 볼록 다각형이 아니다.

조금만 생각해 보면 다각형의 모든 내각이 180도 이하일 때 볼록 다각형이 된다는 것을 알 수 있다. 편의상 이 문제에서는 180도 미만인 경우만을 볼록 다각형으로 한정하도록 한다.

2차원 평면에 N개의 점이 주어졌을 때, 이들 중 몇 개의 점을 골라 볼록 다각형을 만드는데, 나머지 모든 점을 내부에 포함하도록 할 수 있다. 이를 볼록 껍질 (CONVEX HULL) 이라 한다. 아래 그림은 N=10인 경우의 한 예이다.

점의 집합이 주어졌을 때, 볼록 껍질을 이루는 점의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 주어지는 모든 점의 좌표는 다르다고 가정해도 좋다. x좌표와 y좌표의 범위는 절댓값 40,000을 넘지 않는다. 입력으로 주어지는 다각형의 모든 점이 일직선을 이루는 경우는 없다.

출력

첫째 줄에 볼록 껍질을 이루는 점의 개수를 출력한다.

볼록 껍질의 변에 점이 여러 개 있는 경우에는 가장 양 끝 점만 개수에 포함한다.

 

1) long long = int + int

만약  int + int 범위가 int 범위를 넘어서면 값 깨짐.

int + int는 우선적으로 int로 캐스팅되어 담긴 후 long long에 저장되기 때문.

2) 

m.blog.naver.com/kks227/220444892479

[1708번] 볼록 껍질

 

1. 가장 바깥 점을 구한다. (y가 가장 낮고 x가 가장 작은 점)

2. 해당 점을 기준으로 각도가 가장 작은 순으로 정렬한다. (이때 각도는 반시계 방향으로 이루어야 함.)

기준점을 x 축과 평행한 선분위에 위치한다고 봤을 떄 0 ~ 180도 범위내에 다음 점과 이루는 각도가 있기 위해.

3. 기준 점과 각도가 가장 작은 점을 stack에 넣고 그 다음 점부터 검증.

stack 사이즈가 2이상일 때 , 가장 위의 두점과 현재 검색중인 점이 반시계 방향이라면 괜찮지만 시계방향이라면

현재 탐색점이 무조건 테두리 밖에 있게 되는 것이므로 두번 째 점을 제거하고 현재 탐색점만 테두리에 포함시킴.

 

 

 

#include<iostream> 
#include<queue>
#include<stack>
#include<vector>
#include<string.h>
#include<algorithm>
#include<string>
using namespace std;
struct pos
{
	int x, y;
};
vector<pos> vec;
bool compare_pos(pos p1, pos p2)
{
	if (p1.y != p2.y)
	{
		return p1.y < p2.y;
	}
	else
	{
		return p1.x < p2.x;
	}
}
long long ccw(pos p1, pos p2, pos p3)
{
	//음수 시계 
	//양수 반시계 
	//0 평행
	return (p1.x * p2.y + p2.x * p3.y + p3.x * p1.y - (p1.y * p2.x + p2.y * p3.x + p3.y * p1.x));
}

bool compare_rad(pos p1, pos p2)
{
	long long cc = ccw(vec[0], p1, p2);
	if (cc)
		return cc > 0;
	else
		return p1.x + p1.y < p2.x + p2.y;
}

int N;
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	
	
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		int y, x;
		cin >> y >> x;
		vec.push_back({ y,x });
	}
	stack<pos> sta;
	sort(vec.begin(), vec.end(), compare_pos);
	sort(vec.begin() + 1, vec.end(), compare_rad);
	sta.push(vec[0]);
	sta.push(vec[1]);
	pos first, second;
	for (int i = 2; i < N; i++)
	{
		while (sta.size() >= 2)
		{
			second = sta.top();
			sta.pop();
			first = sta.top();
			if (ccw(first, second, vec[i]) > 0)
			{
				sta.push(second);
				break;
			}
		}
		sta.push(vec[i]);
	}
	cout << sta.size();
}