Cod sursă (job #261855)

#include <bits/stdc++.h>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
const int maxn = 120005;
pair <int, int> v[maxn];
int pus[maxn];
int stk[maxn];

inline bool det(int x1, int y1, int x2, int y2, int x3, int y3)
{
    if((x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1) <=0)
        return 0;
    return 1;
}

int sz = 0;
inline void push(int x)
{
    stk[++sz] = x;
    pus[x] = 1;
}

inline void pop()
{
    pus[stk[sz]] = 0;
    sz--;
}

int main()
{
    int n;
    in >> n;
    for(int i = 1; i <= n; i++)
        in >> v[i].first >> v[i].second;
    sort(v + 1, v + n + 1);
    push(1);
    for(int i = 2; i <= n; i++)
    {
        pair <int, int> x = v[stk[sz - 1]];
        pair <int, int> y = v[stk[sz]];
        while(sz >= 2 && !det(x.first, x.second, y.first, y.second, v[i].first, v[i].second))
        {
            pop();
            x = v[stk[sz - 1]];;
            y = v[stk[sz]];
        }
        push(i);
    }
    for(int i = n - 1; i >= 1; i--)
    {
        pair <int, int> x = v[stk[sz - 1]];
        pair <int, int> y = v[stk[sz]];
        if(!pus[i])
        {
            while(sz >= 2 && !det(x.first, x.second, y.first, y.second, v[i].first, v[i].second))
            {
                pop();
                x = v[stk[sz - 1]];;
                y = v[stk[sz]];
            }
            push(i);
        }
    }
    pair <int, int> x = v[stk[sz - 1]];
    pair <int, int> y = v[stk[sz]];
    while(sz >= 2 && !det(x.first, x.second, y.first, y.second, v[1].first, v[1].second))
    {
        pop();
        x = v[stk[sz - 1]];;
        y = v[stk[sz]];
    }
    out << sz << "\n";
    for(int i = 1; i <= sz; i++)
        out << v[stk[i]].first << " " << fixed << v[stk[i]].second << "\n";
    return 0;
}