CONVEXHULL (Bao lồi)

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

using ll = long long;
using ld = long double;
using pii = pair<int, int>;

const int maxN = 1e5 + 5;
const int INF = 1e9 + 7;

struct point {
    long long x, y;
};

bool xetx(point a, point b) { return (a.x < b.x) || (a.x == b.x && a.y < b.y); }
bool xety(point a, point b) { return (a.y < b.y) || (a.y == b.y && a.x < b.x); }

bool CW(point a, point b, point c) { // Cùng chiều kim đồng hồ
    return a.x*(c.y-b.y) + b.x*(a.y-c.y) + c.x*(b.y-a.y) > 0;
}

bool CCW(point a, point b, point c) { // Ngược chiều kim đồng hồ
    return a.x*(c.y-b.y) + b.x*(a.y-c.y) + c.x*(b.y-a.y) < 0;
}

long double Sdagiac(vector<point> &a) {
    long double x = 1.0;
    long double S = 0.0;
    a[a.size()] = a[0];
    for (int i = 0; i < a.size(); ++i)
        S += x * (a[i+1].x - a[i].x) * (a[i+1].y + a[i].y);
    return (S > 0) ? (S / 2.0) : (-S / 2.0);
}

void CONVEXHULL(vector<point> &a) {
    if (a.size() == 1)
        return;

    sort (a.begin(), a.end(), &xetx);

    point p1 = a[0], p2 = a.back();

    vector<point> up, down;
    up.push_back(p1);
    down.push_back(p1);

    for (size_t i = 1; i < a.size(); ++i) {
        // Chuỗi trên
        if (i == a.size()-1 || CW(p1, a[i], p2)) {
            while (up.size() >= 2 && !CW(up[up.size()-2], up[up.size()-1], a[i]))
                up.pop_back();
            up.push_back(a[i]);
        }

        // Chuỗi dưới
        if (i == a.size()-1 || CCW(p1, a[i], p2)) {
            while (down.size() >= 2 && !CCW(down[down.size()-2], down[down.size()-1], a[i]))
                down.pop_back();
            down.push_back(a[i]);
        }
    }

    // Gộp 2 chuỗi
    a.clear();
    for (int i = 0; i < down.size()-1; ++i)
        a.push_back(down[i]);
    for (int i = up.size()-1; i > 0; --i)
        a.push_back(up[i]);

    // In đáp án
    long long ans = a.size();

    cout << ans << '\n';
    cout << fixed << setprecision(1) << Sdagiac(a) << '\n';

    long long mx = INF, my = INF, id = -1;
    for (int i = 0; i < ans; ++i)
        my = min(my, a[i].y);
    for (int i = 0; i < a.size(); ++i)
        if (a[i].y == my && mx > a[i].x)
            mx = a[i].x, id = i;
    for (int i = 0; i < ans; ++i) {
        cout << a[id%ans].x << ' ' << a[id%ans].y << '\n';
        ++id;
    }
}

int n;
vector<point> Points;

int main() {
#ifdef LOCAL
    freopen("in2.txt", "r", stdin);
#else
    freopen("CONVEXHULL.inp", "r", stdin);
    freopen("CONVEXHULL.out", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 0; i < n; i++) {
        point a; cin >> a.x >> a.y;
        Points.push_back(a);
    }

    CONVEXHULL(Points);

    return 0;
}