Cod sursă (job #807219)

#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#define nl '\n'

using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

const int NMAX = 100005;

int n, ind = 1;

struct Point
{
    int x, y;
};
Point points[NMAX];
vector<int> st;

long long int det(const Point& A, const Point& B, const Point& C)
{
    return 1LL*(A.x-B.x)*(B.y-C.y)-1LL*(A.y-B.y)*(B.x-C.x);
}

long long int dist(const Point& A, const Point& B)
{
    return 1LL*(A.x-B.x)*(A.x-B.x)+1LL*(A.y-B.y)*(A.y-B.y);
}

bool cmp(const Point& A, const Point& B)
{
    long long int x = det(points[1], A, B);
    if (x == 0)
        return dist(points[1], A) < dist(points[1], B);
    return x > 0;
}

int main()
{
    fin >> n;
    for (int i = 1; i <= n; i++)
    {
        int x, y;
        fin >> x >> y;
        points[i] = {x, y};
        if ((points[i].y < points[ind].y) || (points[i].y == points[ind].y && points[i].x < points[ind].x))
            ind = i;
    }
    swap(points[1], points[ind]);
    sort(points+2, points+1+n, cmp);
    st.push_back(1);
    st.push_back(2);
    for (int i = 3; i <= n; i++)
    {
        while (st.size() >= 2 && det(points[st[st.size()-2]], points[st[st.size()-1]], points[i]) <= 0)
            st.pop_back();
        st.push_back(i);
    }
    fout << st.size() << nl;
    for (int i = 0; i < st.size(); i++)
        fout << points[st[i]].x << ' ' << points[st[i]].y << nl;
    return 0;
}