Cod sursa(job #277543)

Utilizator floringh06Florin Ghesu floringh06 Data 11 martie 2009 19:42:02
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define FIN "infasuratoare.in"
#define FOUT "infasuratoare.out"
#define MAX_N 120005

typedef struct point
{
        double x, y;
};

point P[MAX_N];
int S[MAX_N];

int N, tp;

struct cmp
{
       bool operator () (const point &a, const point &b)
       {
            if ((double) (a.x - P[1].x)*(b.y - P[1].y) > (double) (b.x - P[1].x)*(a.y - P[1].y)) return 1;
            return 0;
       }
};

    inline int rotate (int a, int b, int c)
    {
           if ((P[a].x - P[c].x) * (P[b].y - P[c].y) - (P[b].x - P[c].x) * (P[a].y - P[c].y) > 0) return 0;
           return 1;
    }   

    int main ()
    {
        int i, m;
        freopen (FIN, "r", stdin);
        freopen (FOUT, "w", stdout);
        
        scanf ("%d", &N);
        for (i = 1; i <= N; ++i)
            scanf ("%lf %lf", &P[i].x, &P[i].y);
            
        for (i = 2, m = 1; i <= N; ++i)
            if (P[i].y < P[m].y) m = i;
               else 
                    if (P[i].y == P[m].y && P[i].x < P[m].x) m = i;
               
        point p = P[1]; P[1] = P[m], P[m] = p;
        sort (P + 2, P + N + 1, cmp());
        
        S[tp = 1] = 1;
        for (i = 1; i <= N; ++i)
        {
            while (tp >= 2 && rotate (S[tp - 1], S[tp], i)) --tp;
            S[++tp] = i;
        }
        
        printf ("%d\n", tp);
        for (i = 1; i <= tp; ++i)
            printf ("%lf %lf\n", P[S[i]].x, P[S[i]].y);
        
        return 0;
    }