BOJ - 볼록 껍질(1708)

문제(링크)
볼록 껍질(Convex Hull) 문제였습니다. 다음과 같이 진행합니다.

1. 기준점을 잡는다 -> y 가 가장 작은 점, y 가 같다면 x가 가장 작은 점
2. 점들을 반시계 방향으로 정렬한다. -> CCW를 이용해 기준점, p1, p2를 비교해
세 점이 반시계 방향이라면 True, 시계 방향이라면 False, 일직선일 때 p1이 기준점과
가까우면 True, 멀면 False을 리턴하는 Comparator로 정렬합니다.
3. 정렬된 점들에 대해 그라함 스캔 알고리즘을 사용합니다.

- 스택의 마지막 - 1 = first
- 스택의 마지막 = second
- 현재 비교하는 점 = next

위 세 점 first, second, next에 대해 CCW를 수행합니다.
CCW > 0  -> 스택에 next를 넣습니다.
CCW <= 0 -> 볼록껍질이 아니므로 이전의 first, second로 되돌리기 위해 스택을 pop 합니다.
(이 작업을 CCW > 0 이 될 때까지 수행합니다.)

남은 스택의 크기가 정답이 됩니다.

#include<iostream>
#include<algorithm>
#include<math.h>
#include<string>
#include<string.h>
#include<vector>
using namespace std;
#define FIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pii pair<int, int>
#define pll pair<long long, long long>
#define ll long long

int N;
vector <pll> vt;
pll start = make_pair(100001, 100001);

void findStart() {

 for (int i = 0; i < N; i++)
 {
  int x = vt[i].first;
  int y = vt[i].second;

  if (start.second > y) {
   start.first = x;
   start.second = y;
  }
  else if (start.second == y) {
   if (start.first > x) {
    start.first = x;
    start.second = y;
   }
  }
 }
}

ll dist(pll p1, pll p2) {
 return (p2.first - p1.first) * (p2.first - p1.first) + (p2.second - p1.second) * (p2.second - p1.second);
}

int CCW(pll p1, pll p2, pll p3) {
 ll S = (p2.first - p1.first) * (p3.second - p1.second) - (p2.second - p1.second) * (p3.first - p1.first);

 if (S > 0) return 1;
 else if (S == 0) return 0;
 else
  return -1;
}

int myCom(pll p1, pll p2) {
 int ret;
 int com = CCW(start, p1, p2);

 if (com == 0) {
  ret = (dist(start, p1) < dist(start, p2));
 }
 else if (com == 1) {
  ret = 1;
 }
 else {
  ret = 0;
 }
 return ret;
}

int main(void) {
 FIO;

 cin >> N;

 int ans = 0;

 for (int i = 0; i < N; i++)
 {
  int x, y;
  cin >> x >> y;

  vt.push_back(make_pair(x, y));
 }

 findStart();

 sort(vt.begin(), vt.end(), myCom);

 vector<pll> st;
 st.push_back(vt[0]);

 for (int i = 1; i < vt.size(); i++)
 {

  pll next = vt[i];

  while (st.size() > 1 && CCW(st[st.size() - 2], st[st.size() - 1], next) <= 0) {
   st.pop_back();
  }
  st.push_back(next);
 }

 cout << st.size();
}