Cod sursa(job #1111257)

Utilizator mirceadinoMircea Popoveniuc mirceadino Data 18 februarie 2014 19:09:50
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include<cstdio>
#include<algorithm>
#define x first
#define y second

using namespace std;

typedef pair<double,double> Point;
const int NMAX = 120000+2;

int N;
int S[NMAX],top;
Point V[NMAX];

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

inline bool cmp(Point A,Point B)
{
    return CrossProduct(V[1],A,B)<0;
}

int main()
{
    int i,p=1;

    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",&V[i].x,&V[i].y);
        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,cmp);

    //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++)
    {
        while(CrossProduct(V[S[top-1]],V[S[top]],V[i])>0 && top>=2) top--;
        S[++top]=i;
    }

    //Afisam solutia

    printf("%d\n",top);

    for(i=top; i>=1; i--)
        printf("%lf %lf\n",V[S[i]].x,V[S[i]].y);

    return 0;
}