Cod sursă (job #816378)

#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");

struct pnt
{
    long long x;
    long long y;
} p[100001];

pnt stiva[100001];
long long top = 0;

long long cross_prod(pnt a, pnt b, pnt c)
{
    long long delta = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
    if (delta > 0)
    {
        return 1; /// trig
    }
    else if (delta == 0)
    {
        return 0; /// col
    }
    else if (delta < 0)
    {
        return -1; /// clockwise
    }
}

long long dist(pnt a, pnt b)
{
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

bool cmp(pnt a, pnt b)
{
    if (cross_prod(p[1], a, b) > 0)
    {
        return true;
    }
    else if (cross_prod(p[1], a, b) == 0)
    {
        return dist(p[1], a) < dist(p[1], b);
    }
    else
    {
        return false;
    }
}

int main()
{
    long long n;
    cin >> n;
    long long mini = 1;
    for (long long i = 1; i <= n; i ++)
    {
        cin >> p[i].x >> p[i].y;
        if (p[i].y < p[mini].y)
        {
            mini = i;
        }
        else if (p[i].y == p[mini].y)
        {
            if (p[i].x < p[mini].x)
            {
                mini = i;
            }
        }
    }
    swap(p[mini], p[1]);
    sort(p + 2, p + n + 1, cmp);
//    for (long long i = 1; i <= n; i ++)
//    {
//        cout << p[i].x << " " << p[i].y << "\n";
//    }
    top ++;
    stiva[top] = p[1];
    top ++;
    stiva[top] = p[2];
    for (long long i = 3; i <= n; i ++)
    {
        if (cross_prod(stiva[top - 1], stiva[top], p[i]) > 0 || top == 1)
        {
            top ++;
            stiva[top] = p[i];
        }
        else
        {
            while (cross_prod(stiva[top - 1], stiva[top], p[i]) <= 0 && top > 1)
            {
                top --;
            }
            top ++;
            stiva[top] = p[i];
        }
    }
    cout << top << "\n";
    for (long long i = 1; i <= top; i ++)
    {
        cout << stiva[i].x << " " << stiva[i].y << "\n";
    }
    return 0;
}