CONVEXHULL.cpp

#include <bits/stdc++.h>
using namespace std;

#define point pair<int, int>
#define x first
#define y second

bool cross(point o, point a, point b) {
    return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x) <= 0;
}

void andrew(vector<point> &a) {
    sort(a.begin(), a.end());
    int n = a.size(), m = 0;
    vector<point> b(n + 1);
    for (int i = 0; i < n; i++) {
        while (m >= 2 && cross(b[m - 2], b[m - 1], a[i])) m--;
        b[m++] = a[i];
    }
    for (int i = n - 2, t = m + 1; i >= 0; i--) {
        while (m >= t && cross(b[m - 2], b[m - 1], a[i])) m--;
        b[m++] = a[i];
    }
    a.resize(1);
    for (int i = 1; i < m - 1; i++) {
        if (b[i] != b[i + 1]) a.push_back(b[i]);
    }
}

int main(){
#ifdef _DEBUG
    freopen("in", "r", stdin);
#endif
    ios::sync_with_stdio(0); cin.tie(0);
    int n;
    while (cin >> n, n) {
        vector<point> a(n);
        for (int i = 0; i < n; i++) {
      cin >> a[i].x >> a[i].y;
    }
        andrew(a);
        cout << a.size() << '\n';
        for (int i = 0; i < a.size(); i++) {
            cout << a[i].x << ' ' << a[i].y << '\n';
    }
    }
}