Cod sursă (job #444755)

#include <bits/stdc++.h>
#define eps 1e-12

using namespace std;

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

int const NMAX = 100005;

int n, h;
int s[NMAX], ok[NMAX];

struct Punct
{
    double x,y;
};
Punct p[NMAX], v[NMAX];

void Read()
{
    int i;
    fin >> n;
    for (i = 1; i <= n; i++)
        fin >> v[i].x >> v[i].y;
}

inline int CMP1(double a, double b)
{
    if (a + eps < b) return 1;
    if (b + eps < a) return -1;
    return 0;
}

bool CMP(const Punct &a, const Punct &b)
{
    /**
        functia de comparare a coordonatelor punctelor:
        cresator dupa x si, in caz de egalitate, crescator dupa y
    */
    int t;
    t = CMP1(a.x, b.x);
    if (t != 0) return (t == 1);
    return (CMP1(a.y, b.y) == 1);
}

int Semn(Punct a, Punct b, Punct c)
{
    /**
        se verifica daca punctul C(care este testat) se afla de o parte sau alta a dreptei AB
        utilizandu-se formula cu determinanti a ariei triunghiului ABC
    */
    double A, B, C;
    A = a.y - b.y;
    B = b.x - a.x;
    C = a.x * b.y - b.x * a.y;
    return CMP1(A * c.x + B * c.y + C, 0);
}

void Do()
{
    int k, q, i;

    ///se sorteaza punctele dupa x, iar in caz de egalitate, dupa y
    sort(v + 1, v + n + 1, CMP);

    s[1] = 1;
    s[2] = 2;

    /**
        se initializeaza stiva S, in care se introduce cel mai din stanga punct,
        care se va afla sigur pe infasuratoare, si cel de-al 2-lea punct,
        care urmeaza sa fie verificat
	*/

    ok[2] = 1;
    /// vectorul de ok[], va contoriza introducerea sau scoaterea unui punct din stiva

    k = 2;
    /// k = nr de elemente din stiva

    i = 3;
    /**
        i = indicele punctului care urmeaza sa fie verificat
            pentru a stabili daca se afla pe infasuratoare
    */

    q = 1;

    /**
        q = 1  -> incrementarea indicelui punctului;
        q = -1 -> decrementarea indicelui punctului cand se ajunge la cel mai
                    din dreapta punct (i == n)
    */

    while (!ok[1]) /// nu s-a inchis poligonul convex
    {
        /// se cauta un punct neutilizat inca pe infasuratoare

        while (ok[i])
        {
            if (i == n) q = -1;
            i += q;
        }

        ///verificare daca punctul respecta proprietatea prin functia "semn"

        while (k >= 2 && Semn(v[s[k-1]], v[s[k]], v[i]) == -1)
        {
            ok[s[k--]] = 0; ///scoatere din stiva
        }
        s[++k] = i; ///introducerea punctului valid in stiva
        ok[i] = 1;
    }
    h = k - 1; /// h = nr de puncte de pe infasuratoare
}

void Write()
{
    int i;
    fout << h << "\n";
    for (i = 2; i <= h + 1; i++)
        fout << v[s[i]].x << " " << v[s[i]].y << "\n"; /// punctele de pe infasuratoare
}

int main ()
{
    Read();
    Do();
    Write();
    return 0;
}