BOJ 1708번 볼록 껍질

BOJ : https://www.acmicpc.net/problem/1708

 

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <set>
#include <cmath>
#include <limits>
#include <cstring>
#include <string>
using namespace std;
typedef long long ll;
struct point {
    ll x, y;
    ll p = 0, q = 0;
}p[100001];
 
bool cmp(point& a, point& b) {
    if (1LL * a.p * b.q != 1LL * a.q * b.p) return a.q * b.p < a.p * b.q;
    if (a.x != b.x) return a.x < b.x;
    return a.y < b.y;
}
 
ll ccw(point& a, point& b, point& c) {
    return 1LL * (b.x - a.x) * (c.y - a.y) - 1LL * (b.y - a.y) * (c.x - a.x);
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
    int N; cin >> N;
    for (int i = 0; i < N; i++) cin >> p[i].x >> p[i].y;
 
    sort(p, p + N, cmp);
    for (int i = 1; i < N; i++) {
        p[i].p = p[i].x - p[0].x;
        p[i].q = p[i].y - p[0].y;
    }
    sort(p + 1, p + N, cmp);
    stack<int> s;
    s.push(0), s.push(1);
    int next = 2;
    while (next < N) {
        while (s.size() >= 2) {
            int second = s.top();
            s.pop();
            int first = s.top();
            if (ccw(p[first], p[second], p[next]) > 0) {
                s.push(second);
                break;
            }
        }
        s.push(next++);
    }
    cout << s.size();
    return 0;
}