Cod sursa(job #1042672)

Utilizator mirceadinoMircea Popoveniuc mirceadino Data 27 noiembrie 2013 16:17:07
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include<cstdio>
#include<algorithm>
#include<utility>

#define NMAX 120000+5
#define PDD pair<double,double>
#define x first
#define y second

using namespace std;

int N,top;
PDD V[NMAX];
PDD ST[NMAX];

inline double crossproduct(PDD A,PDD B,PDD C){return (B.x-A.x)*(C.y-A.y)-(C.x-A.x)*(B.y-A.y);}

inline bool crit(PDD A,PDD B){return crossproduct(V[1],A,B)<0;}

int main()
{
    int i,p=1;
    double a,b;

    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);

    scanf("%d",&N);

    //1. Alegem un punct extrem (cel mai din stanga) care cu
    //siguranta face parte din infasuratoare

    for(i=1;i<=N;i++)
    {
        scanf("%lf%lf",&a,&b);
        V[i]=make_pair(a,b);
        if(V[i]<V[p]) p=i;
    }

    //2. Sortam punctele dupa unghiul polar pe care il fac
    //cu punctul P selectat

    swap(V[1],V[p]);
    sort(V+2,V+N+1,crit);

    //3. Analizam tripletele de puncte consecutive Pi,Pi+1,
    //Pi+2. Daca face intoarcere la dreapta, atunci Pi+1 nu
    //poate face parte din infasuratoare

    for(i=1;i<=N;i++)
    {
        for(;top>=2 && crossproduct(ST[top-1],ST[top],V[i])>0;top--);
        ST[++top]=V[i];
    }

    //Afisam solutia

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