[BOJ] 1708 볼록 껍질

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

 

 

 

문제 풀이:

Convex Hull 알고리즘 중 Graham's Scan 방법을 이용하여 풀었다.

(다른 방법으로는 monotone chain convex hull 방법이 있다)

 

입력 받은 좌표 중 가장 작은 y값을 가진 점 중 가장 작은 x값을 가진 점을 기준점으로 삼는다.

그 기준점과 모든 점과의 기울기를 기준으로 좌표를 정렬한다. 

 

기울기가 작은 점들부터 비교 연산을 시작한다.

처음에 벡터(나는 벡터를 스택처럼 사용)에 기준점과 기울기가 가장 작은 점, 두 점을 백터에 넣는다.

그 후 인덱스(idx)를 증가시켜가며 현재 벡터의 top에 있는 2점을 기준으로 ccw가 양수이면 해당 좌표의 인덱스를 벡터에 넣고 idx++

ccw가 음수이면 잘못된 점을 넣은 것이므로 idx는 유지하고 벡터 pop_back()

ccw가 0이면 일직선에 있는 것이므로 벡터 pop_back()하고 현재 값 넣고 idx++

 

 

소스 코드:

typedef long double ld;
typedef pair<ld, ld> P;
typedef pair<P, P> PP;
vector<P> v;
vector<int> st;
int startPoint,res;
ld x, y;
bool cmp(const P a, const P b) {
	if ((x - b.first)*(y - a.second) == (x - a.first)*(y - b.second)) {
		if (a.second == b.second)
			return a.first< b.first;
		else
			return a.second < b.second;
	}
	else {
		return (x - b.first)*(y - a.second) < (x - a.first)*(y - b.second);			
	}
}
ld ccw(PP a,P b) {
	P a1 = a.first,a2=a.second;
	ld ccw11 = (a1.first*a2.second + a2.first*b.second + b.first*a1.second)
		- (a2.first*a1.second + b.first*a2.second + a1.first*b.second);

	return ccw11;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		ld q, w;
		cin >> q >> w;
		v.push_back({ q,w });
		if (v[startPoint].second > w ||(v[startPoint].second==w && v[startPoint].first> q)) {
			startPoint = i;
		}
	}
	x = v[startPoint].first;
	y = v[startPoint].second;
	sort(v.begin(), v.end(), cmp);
	st.push_back(0);
	st.push_back(1);
	int t = 1;
	int idx = 2;
	while (1) {
		if (idx == n) break;
		ld ccwV = ccw(make_pair(v[st[t-1]], v[st[t]]), v[idx]);
		if (ccwV>0) {
			st.push_back(idx);
			idx++;
			t++;
		}
		else if (ccwV == 0) {
			st.pop_back();
			st.push_back(idx);
			idx++;
		}
		else {
			st.pop_back();
			t--;
		}
	}
	cout << st.size() << '\n';
	return 0;
}