Cod sursa(job #1344953)

Utilizator raztaapDumitru raztaap Data 17 februarie 2015 09:35:16
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <cstdio>
#include <algorithm>
using namespace std;
#define MAXN 120100
struct puncte{double x; double y;};
puncte v[MAXN], ST[MAXN];
int n, vf;
void citire()
{
    int i;
    scanf("%d", &n);
    for(i=1;i<=n;++i)
        scanf("%lf%lf", &v[i].x, &v[i].y);

}
inline double cross_product(const puncte& A, const puncte& B, const puncte& C) {
    return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}

inline int cmp(const puncte& p1, const puncte& p2) {
    return cross_product(v[1], p1, p2) < 0;
}
void sort_puncte()
{
    int pos = 1;
    puncte aux;
    for (int i = 2; i <= n; ++i)
        if (v[i].x < v[pos].x)
            pos = i;
    aux=v[1];
    v[1]=v[pos];
    v[pos]=aux;
    sort(v + 2, v + n + 1, cmp);
}

void infas()
{
    sort_puncte();
    ST[1]=v[1];
    ST[2]=v[2];
    vf=2;
    int i;
    for(i=3;i<=n;++i)
    {
        while(vf>=2&&cross_product(ST[vf-1], ST[vf], v[i])>0)
            --vf;
        ST[++vf]=v[i];
    }
}
void afisare()
{
    int i;
    printf("%d\n", vf);
    for(i=vf;i>=1;--i)
        printf("%.9f %.9f\n", ST[i].x, ST[i].y);
}
void rezolva_problema()
{
    citire();
    infas();
    afisare();
}
int main()
{
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);
    rezolva_problema();
    return 0;
}