Cod sursă (job #77607)

#include <stdio.h>
#include <vector>
#include <algorithm>
#define MAX_N 100000
using namespace std;

struct punct
{
    double x;
    double y;
};

vector<punct> points(MAX_N);
int n, indexmin, st[MAX_N], vf;
punct pmin;

double det(punct a, punct b, punct c)
{
    return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}

bool rule(const punct &a, const punct &b)
{
    return det(pmin, a, b)>0;
}

int main()
{
    FILE *in, *out;
    in = fopen("infasuratoare.in", "r");
    out = fopen("infasuratoare.out", "w");




    fscanf(in, "%d", &n);
    punct p;
    for(int i=0; i<n; i++)
    {
        fscanf(in, "%lf%lf", &p.x, &p.y);
        points[i].x=p.x;
        points[i].y=p.y;
        if(i==0)
        {
            pmin.y=p.y;
            pmin=points[i];
            indexmin=i;
        }
        if(pmin.y>p.y || (pmin.y==p.y && pmin.x>p.x))
        {
            pmin=points[i];
            indexmin=i;
        }
    }

    points.erase(points.begin()+indexmin);

    points[n-1]=pmin;

    std::sort(points.begin(), points.begin() + n-1, rule);

    st[0]=n-1;
    st[1]=0;
    vf=1;
    for(int i=1; i<n-1; i++)
    {
        vf++;
        st[vf]=i;
        while(det(points[st[vf-2]], points[st[vf-1]], points[st[vf]])<=0 && vf>1)
        {
            st[vf-1]=st[vf];
            vf--;
        }
    }

    while(det(points[st[vf-1]], points[st[vf]], points[st[0]])<=0 && vf>1)
        vf--;

    fprintf(out, "%d\n", vf+1);
    for(int i=0; i<=vf; i++)
    {
        fprintf(out, "%f %f\n", points[st[i]].x, points[st[i]].y);
    }

    fclose(in);
    fclose(out);

    return 0;
}