Cod sursă (job #817800)

#include <bits/stdc++.h>

using namespace std;

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

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

pnt stiva[100001];
long long varf = 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;

    else if (delta == 0)
        return 0;

    else if (delta < 0)
        return -1;

}

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(v[1], a, b) > 0)
        return true;

    else if (cross_prod(v[1], a, b) == 0)
        return dist(v[1], a) < dist(v[1], b);

    else
        return false;

}

int main()
{
    long long n;

    fin >> n;

    long long mini = 1;
    for (long long i = 1; i <= n; i ++)
    {
        fin >> v[i].x >> v[i].y;

        if (v[i].y < v[mini].y)
            mini = i;

        else if (v[i].y == v[mini].y)
            if (v[i].x < v[mini].x)
            {
                mini = i;
            }
    }
    swap(v[mini], v[1]);
    sort(v + 2, v + n + 1, cmp);

    varf ++;
    stiva[varf] = v[1];
    varf ++;
    stiva[varf] = v[2];

    for (long long i = 3; i <= n; i ++)
    {
        if (cross_prod(stiva[varf - 1], stiva[varf], v[i]) > 0 || varf == 1)
        {
            varf ++;
            stiva[varf] = v[i];
        }
        else
        {
            while (cross_prod(stiva[varf - 1], stiva[varf], v[i]) <= 0 && varf > 1)
                varf --;

            varf ++;
            stiva[varf] = v[i];
        }
    }
    fout << varf << "\n";

    for (long long i = 1; i <= varf; i ++)
        fout << stiva[i].x << " " << stiva[i].y << "\n";

}