이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 52 번째 글 입니다.
목차
골드1 : 기하 문제이다.
생각
볼록 껍질, Convex Hull이라 한다. 이 알고리즘에서 유명한 것을 그라함 스캔 알고리즘인데, 해당 동영상을 봐보자.
이것과 같은 알고리즘을 구현하기 위해서는 다음과 같은 절차를 거쳐야 한다.
- 가장 y가 작은 점을 구한다.
- 그 점을 기준으로 직선의 각을 기준으로 정렬한다.
- 각이 가장 작은 점부터 조사하면서 볼록 껍질인지 아닌지 확인하고 추가한다.
이 때, 각을 기준으로 정렬을 수행해야 하는데, 각은 double 형이라 이를 정렬하는데 좋지 않다. 일단 구하기도 어렵고 같은 선상에 있을 때 골치가 아프다..
그래서 이 때 각을 대변해 줄 수 있는 다른 지표로 외적의 부호를 사용한다. 이 부분이 달달한 부분인데, 외적의 값은 x, y축을 기저로 보았을 때, 시계 방향, 반시계 방향을 대변해 준다. 이 때, 특정 두 점과의 외적을 수행하면 서로의 상대적 위치를 알 수 있다.
이 연산을 점들을 각 순서로 정렬하는 비교 연산으로 사용하자.
Code
#include<iostream>
#include<vector>
#include<string>
#include<cstring>
#include<iomanip>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
struct Point{
ll x, y;
};
vector<Point> p;
int N;
ll ccw(Point p1, Point p2, Point p3){
return p1.x*p2.y + p2.x*p3.y + p3.x*p1.y - (p2.x*p1.y + p3.x*p2.y + p1.x*p3.y);
}
bool compareMinelement(Point p1, Point p2){
if (p1.y == p2.y) return p1.x < p2.x;
else return p1.y < p2.y;
}
bool compareCCW(Point p1, Point p2){
ll cp = ccw(p[0], p1, p2);
if (cp == 0) return (p1.x + p1.y) < (p2.x + p2.y);
return cp > 0;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> N;
p.resize(N);
for (int i = 0; i < N; i++) {
cin >> p[i].x >> p[i].y;
}
sort(p.begin(), p.end(), compareMinelement);
sort(p.begin()+1, p.end(), compareCCW);
vector<Point> v;
v.push_back(p[0]);
v.push_back(p[1]);
// 이 for문은 세점 중 가장 바깥쪽 점을 의미
for (int i = 2; i < N; i++) {
// 볼록을 찾을 때까지 계속 진행
while (v.size() >= 2) {
// 두개를 본다.
Point p2 = v.back();
v.pop_back();
Point p1 = v.back();
// ccw이면 중간에 있는 점(p2)를 확인된 점으로 판단하고 스택에 넣는다.
if (ccw(p1, p2, p[i]) > 0) {
v.push_back(p2);
break;
}
// ccw가 아니면 p2를 추가하지 말고 p2이전의 2점과 현재 p[i]와 ccw인지 비교한다. (처음으로 돌아간다)
}
// while문을 통과했다면 점이 추가가 된 것이므로 현재 탐색하는 가장 바깥쪽 점도 넣어준다.
v.push_back(p[i]);
}
cout << v.size() << '\n';
}
보다 깔끔한 Convex Hull Code
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
struct Point {
ll x, y;
Point(ll a, ll b) :x(a), y(b) {};
Point() {};
bool operator<(const Point &rhs) const {
if (x != rhs.x) return x < rhs.x;
return y < rhs.y;
}
};
vector<Point> point;
ll ccw(Point pt1, Point pt2, Point pt3) {
ll ret = pt1.x*pt2.y + pt2.x*pt3.y + pt3.x*pt1.y;
ret -= (pt2.x*pt1.y + pt3.x*pt2.y + pt1.x*pt3.y);
return ret;
}
ll dist(Point pt1, Point pt2) {
ll dx = pt2.x - pt1.x;
ll dy = pt2.y - pt1.y;
return dx * dx + dy * dy;
}
int main(){
int N;
cin >> N;
point.resize(N);
for (int i = 0; i < N; i++) {
cin >> point[i].x >> point[i].y;
}
vector<Point> hull;
swap(point[0], *min_element(point.begin(), point.end()));
sort(point.begin() + 1, point.end(), [](Point x, Point y) {
ll cw = ccw(point[0], x, y);
if (cw == 0) return dist(point[0], x) < dist(point[0], y);
return cw > 0;
});
for (auto i : point) {
// hull의 뒤에서 2번째 값, 1번째 값, 그리고 point의 3번째 값을 비교하여
// 반시계가 아니면 hull의 맨 뒤의 점을 뺀다.
// 반시계이면 해당 점을 포함한 상태로 다음점을 비교한다.
while (hull.size() >= 2 && ccw(hull[hull.size() - 2], hull.back(), i) <= 0) {
hull.pop_back();
}
hull.push_back(i);
}
cout << hull.size() << endl;
}