Cod sursă (job #774722)

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define MAX 100000

using namespace std;

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

int64_t n, i, k, cmin, m=1, l=-1;
struct coord{int64_t x, y;};
coord v[MAX], s[MAX];

int64_t dist(coord p1, coord p2)
{
    const int64_t o1=(p1.x-p2.x), o2=(p1.y-p2.y);
    return o1*o1+o2*o2;
}

int64_t orientatie(coord p1, coord p2, coord p3)
{
    int64_t val = (p2.y-p1.y)*(p3.x-p2.x)-(p3.y-p2.y)*(p2.x-p1.x);
    if(val == 0) return 0;
    else return (val > 0 ? 1 : 2);
}

bool compare(const coord i1, const coord i2)
{
    const int64_t o = orientatie(v[0], i1, i2);
    if(!o) return (dist(v[0], i2) >= dist(v[0], i1));
    else return (o == 2);
}

int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(nullptr);
    fout.tie(nullptr);
    fin >> n >> v[0].x >> v[0].y;
    for(i=1; i < n; i++)
    {
        fin >> v[i].x >> v[i].y;
        if((v[i].y < v[cmin].y) || ((v[i].y == v[cmin].y) && (v[i].x < v[cmin].x))) cmin = i;
    }
    swap(v[0], v[cmin]);
    sort(v+1, v+n, compare);
    for(i=1; i < n; i++)
    {
        while((i < n-1) && (!orientatie(v[0], v[i], v[i+1]))) i++;
        v[m++] = v[i];
    }
    s[++l] = v[0];
    s[++l] = v[1];
    s[++l] = v[2];
    for(i=3; i < m; i++)
    {
        while(l && orientatie(s[l-1], s[l], v[i]) != 2) l--;
        s[++l] = v[i];
    }
    fout << l+1 << '\n';
    for(i=0; i <= l; i++) fout << s[i].x << ' ' << s[i].y << '\n';
}