BOJ 2699번 격자점 컨벡스헐

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

 

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <set>
#include <cmath>
#include <limits>
#include <cstring>
#include <string>
using namespace std;
 
struct point {
    int x, y;
    int p = 0, q = 0;
}p[52];
 
bool cmp(point& a, point& b) {
    if (a.p * b.q != a.q * b.p) return a.q * b.p > a.p * b.q;
    if (a.y != b.y) return a.y > b.y;
    return a.x < b.x;
}
 
int ccw(point& a, point& b, point& c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
    int tc; cin >> tc;
 
    while (tc--) {
        int N; cin >> N;
        for (int i = 0; i < N; i++) {
            cin >> p[i].x >> p[i].y;
            p[i].p = p[i].q = 0;
        }
        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() << endl;
        vector<point> v;
        while (!s.empty()) {
            v.push_back(p[s.top()]);
            s.pop();
        }
        for (int i = v.size() - 1; i >= 0; i--) cout << v[i].x << " " << v[i].y << "\n";
    }
 
    return 0;
}