---
# System prepended metadata

title: Untitled

---


## Convex Hull

```c=
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#define MAX 100002
using namespace std;

typedef long long ll;
 
struct INFO {
    int x, y;
    int p, q;
    INFO(int x1 = 0, int y1 = 0) : x(x1), y(y1), p(1), q(0) {}
};
bool comp(const INFO &A, const INFO &B) {
    if (1LL * A.q * B.p != 1LL * A.p * B.q)
        return 1LL * A.q * B.p < 1LL * A.p*B.q;
 
    if (A.y != B.y)
        return A.y < B.y;
 
    return A.x < B.x;
}
ll ccw(const INFO &A, const INFO &B, const INFO &C) {
    return 1LL * (A.x * B.y + B.x * C.y + C.x * A.y - B.x * A.y - C.x * B.y - A.x * C.y);
}

INFO p[MAX];
int main() {
    int n;
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
 
        p[i] = INFO(x, y);
    }
 
    // y좌표, x좌표가 작은 순으로 정렬
    sort(p, p + n, comp);
 
    // 기준점으로부터 상대 위치 계산
    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, comp);
    stack<int> s;
    // 스택에 first, second를 넣어준다.
    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();
            // first, second, next가 좌회전 ( > 0 )이라면 second push
            // 우회전( < 0 )이라면 위의 while문 계속 반복
            if (ccw(p[first], p[second], p[next]) > 0) {
                s.push(second);
                break;
            }
        }
        // next push
        s.push(next++);
    }
    printf("%d", s.size());
    return 0;
}