Cod sursa(job #1098799)

Utilizator mircea.dobreanuMircea Dobreanu mircea.dobreanu Data 5 februarie 2014 11:07:29
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include<cstdio>
#include<algorithm>
#define x first
#define y second
using namespace std;
const int MAXN=120005;
typedef pair<double,double> point;
int n,head;
point p[MAXN],stack[MAXN];

inline void push(point a){stack[++head]=a;}
inline void pop(){--head;}

double cross_product(point O, point A, point B)
{
    point OA,OB;
    OA.x=A.x-O.x;
    OA.y=A.y-O.y;
    OB.x=B.x-O.x;
    OB.y=B.y-O.y;
    return OA.x*OB.y-OA.y*OB.x;
}
bool compare_vectors(point A, point B)
{
    return cross_product(p[1],A,B)<0;
}
int main()
{
    int i,pos=1;
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    scanf("%d",&n);
    for (i=1; i<=n; ++i)
        scanf("%lf%lf",&p[i].x,&p[i].y);

    //sorteaza punctele dupa produsul vectorial OA, OB unde O=p[1]
    for (i=1; i<=n; ++i)
    {
        if (p[pos]>p[i])
            pos=i;
    }
    swap(p[1],p[pos]);
    sort(p+2,p+n+1,compare_vectors);

    //infasuratoarea convexa
    push(p[1]);
    push(p[2]);
    for (i=3; i<=n; ++i)
    {
        while (head>=2 && cross_product(stack[head-1],stack[head],p[i])>0)
            pop();
        push(p[i]);
    }

    printf("%d\n",head);
    for (i=head; i>0; --i)
        printf("%.6lf %.6lf\n",stack[i].x,stack[i].y);
    return 0;
}