Cod sursă (job #807868)

#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

ifstream f ("infasuratoare.in");
ofstream g ("infasuratoare.out");

const int NMAX = 100000;

struct punct {
    int x, y;
};

punct P[NMAX+2], S[NMAX+2];
int N, H;

void afis() {
    g << H << '\n';
    for (int i=1; i<=H; i++)
        g << S[i].x << ' ' << S[i].y << '\n';
}

inline long long patrat(long long x) {
    return x*x;
}

long long distp(const punct &A, const punct &B) {
    return patrat(A.x - B.x) + patrat(A.y-B.y);
}

bool compy(const punct &A, const punct &B) {
    if (A.y == B.y) return A.x < B.x;
    return A.y < B.y;
}

long long det (const punct &A, const punct &B, const punct &C) {
    return 1LL * (A.x - B.x) * (B.y - C.y) - 1LL * (A.y - B.y) * (B.x - C.x);
}

bool compd(const punct &A, const punct &B) {
    long long dd = det(P[1], A, B);
    if (dd == 0)
        return distp(P[1], A) < distp(P[1], B);
    return dd > 0;
}

void citire() {
    f >> N;
    int pmin = 1;
    for (int i=1; i<=N; i++) {
        f >> P[i].x >> P[i].y;
        if (compy(P[i], P[pmin]))
            pmin = i;
    }
    swap(P[1], P[pmin]);
}


void Graham() {
    sort(P+2, P+N+1, compd);
    S[1] = P[1];
    S[2] = P[2];
    H = 2;
    for (int i=3; i<=N+1; i++) {
        while(H >= 2 && det(S[H-1], S[H], P[i]) <= 0)
            H--;
        S[++H] = P[i];
    }
    H--;
}

int main()
{
    citire();
    Graham();
    afis();
    f.close();
    g.close();
    return 0;
}