boj, 백준) 2699. 격자점 컨벡스헐 ( C / C++ )

1. 문제 링크

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

2699번: 격자점 컨벡스헐

2. 문제 개요

좌표가 주어지고 컨벡스 헐을 이루는 점의 개수, 좌표(x, y) 순서를 조건에 맞는 순서대로 출력할 것.

 

조건은

1. 첫 번째 곡짓점은 y좌표가 가장 큰 점이다. 만약, 그러한 점이 2개라면, x가 작은 점이 첫 번째 점이다.

2. 그 다음 점부터는 시계방향 순서이다.

 

 

3. 문제 힌트

평소에 알고 있는 컨벡스 헐 알고리즘인 그라함 스캔 알고리즘은 y좌표가 가장 작고 (y좌표가 같다면) x좌표가 가장 작은 점부터 반시계 방향으로 시작한다. 그런데 문제의 조건은 그 반대인 y가 가장 큰 점이다. 그리고 시계방향이다.

어떻게 좌표를 조작하면 우리가 알고있는 그라함스캔의 조건대로 시작할 수 있을까?

 

대칭에 대해서 잘 생각해보자.

 

4. 문제 풀이

대칭으로 저 조건을 만족시킬 수 있다는것만 빨리 캐치하면 그냥 단순한 컨벡스 헐 알고리즘 구현 문제이다.

 

(종이에 그려가면서 생각하면 쉽습니다.)

 

기존 그라함 스캔 알고리즘은 y좌표가 가장 작은, 만약 y가 같다면 x좌표가 가장작은 좌표로부터 반시계 방향으로 시작한다. 만약 입력을 y대칭의 형태로 받고 기존의 컨벡스 헐 알고리즘을 사용한 뒤 출력할 때 다시 원래의 y값대로 출력해주면 조건에 만족하면서 쉽게 구현할 수 있다.

 

그게 아니라면 좌표의 정렬 조건을 손봐주어야 한다. 

새로운 기준을 잡아서 가장 위의 왼쪽 점을 구한 뒤, 그 점을 기준으로 시계방향으로 정렬하면 된다. 단순하게 알고리즘을 외운 사람은 이 부분을 적용하기 힘들 것이다. 따라서 이번 기회에 정렬하는 원리 및 ccw의 원리(외적)에 대해서 공부하는 것도 좋을 듯하다.

 

코드의 operator < 부분을 손봐주면 된다.

5. 코드

#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

struct Point
{
	int x, y, p, q;

	Point() {}
	Point(int x_, int y_, int p_ = 0, int q_ = 0) :x(x_), y(y_), p(p_), q(q_) {}

	bool operator < (const Point& arg)
	{
		if (1LL * p*arg.q != 1LL * q*arg.p)	return 1LL * p*arg.q - 1LL * q*arg.p > 0;
		if (y != arg.y)	return y < arg.y;
		return x < arg.x;
	}
};
//a->b, a->b
long long ccw(const Point& a, const Point &b, const Point &c)
{
	return 1LL * (b.x - a.x)*(c.y - a.y) - 1LL * (b.y - a.y)*(c.x - a.x);
}

int main()
{
	int t;
	scanf("%d", &t);
	while (t--)
	{
		int n;
		vector<Point> v;

		scanf("%d", &n);
		v.resize(n);

		for (int i = 0; i < n; ++i)
		{
			int x, y;
			scanf("%d %d", &x, &y);
			v[i] = Point(x, -y);	//조건만족을 위해서 y대칭함.
			//y는 가장 큰->작은, 시계 -> 반시계
		}

		sort(v.begin(), v.end());

		for (int i = 1; i < n; ++i)
		{
			v[i].p = v[i].x - v[0].x;
			v[i].q = v[i].y - v[0].y;
		}
		sort(++v.begin(), v.end());

		stack<int> s;
		s.push(0);
		s.push(1);
		int next = 2;
		while (next < n){
			while (s.size() >= 2){
				int first, second;
				second = s.top(); s.pop();
				first = s.top();

				if (ccw(v[first], v[second], v[next]) > 0)
				{
					s.push(second);
					break;
				}
			}
			s.push(next++);
		}
		stack<int> ans;
		while (!s.empty()){
			ans.push(s.top());
			s.pop();
		}

		printf("%d\n", ans.size());
		while (!ans.empty()){
			printf("%d %d\n", v[ans.top()].x, -v[ans.top()].y);
			ans.pop();
		}
			

	}
	
	return 0;
}

6. 결과