Cod sursa(job #1081036)

Utilizator macajouMaca George macajou Data 13 ianuarie 2014 08:50:03
Problema Infasuratoare convexa Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include <cstdio>
#include <algorithm>
#define nmax 120010

using namespace std;

struct punct
{
    double x,y;
}a[nmax];

int n,st[nmax],nr,viz[nmax];

bool cmp(punct a, punct b)
{
    if(a.y==b.y)
       return a.x<b.x;
    return a.y<b.y;
}

void citire()
{
    int i;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%lf%lf",&a[i].x,&a[i].y);

}

bool verif(punct a, punct b, punct c)
{
    if(a.x*b.y+b.x*c.y+a.y*c.x-c.x*b.y-b.x*a.y-c.y*a.x>=0)
       return 1;
    return 0;
}

void infas()
{
    int i;
    st[1]=1;
    st[2]=2;
    viz[2]=1;
    viz[1]=1;
    nr=2;
    for(i=3;i<=n;i++)
        {
            while(!verif(a[st[nr-1]],a[st[nr]],a[i]) && nr>1)
                  viz[st[nr--]]=0;
            st[++nr]=i;
            viz[st[nr]]=1;
        }
    viz[1]=0;
    for(i=n;i>=1;i--)
        if(!viz[i])
           {
               while(!verif(a[st[nr-1]],a[st[nr]],a[i]) && nr>1)
                     viz[nr--]=0;
                st[++nr]=i;
                viz[nr]=1;
           }
}

void afisare()
{
    int i;
    printf("%d\n",nr-1);
    for(i=1;i<nr;i++)
        printf("%lf %lf\n",a[st[i]].x,a[st[i]].y);
}

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

    citire();
    sort(a+1,a+1+n,cmp);
    /*for(int i=1;i<=n;i++)
        printf("%lf %lf\n",a[i].x,a[i].y);*/
    infas();
    afisare();


    return 0;
}