Cod sursă (job #816371)

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

using namespace std;

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

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

pnt stiva[100001];
int top = 0;

int cross_prod(pnt a, pnt b, pnt c)
{
    int 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
    {
        return -1; /// clockwise
    }
}

bool cmp(pnt a, pnt b)
{
    return cross_prod(p[1], a, b) > 0;
}

int main()
{
    int n;
    cin >> n;
    int minx = 1999999999, miny = 1999999999;
    int mini = 1;
    for (int i = 1; i <= n; i ++)
    {
        cin >> p[i].x >> p[i].y;
        if (p[i].y < miny)
        {
            minx = p[i].x;
            miny = p[i].y;
            mini = i;
        }
        else if (p[i].y == miny)
        {
            if (p[i].x < minx)
            {
                minx = p[i].x;
                mini = i;
            }
        }
    }
    swap(p[mini], p[1]);
    sort(p + 2, p + n + 1, cmp);
    top ++;
    stiva[top] = p[1];
    top ++;
    stiva[top] = p[2];
    for (int 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]) == -1)
            {
                top --;
            }
            top ++;
            stiva[top] = p[i];
        }
    }
    cout << top - 1 << "\n";
    for (int i = 1; i < top; i ++)
    {
        cout << stiva[i].x << " " << stiva[i].y << "\n";
    }
    return 0;
}