Cod sursa(job #1377272)

Utilizator Alexa2001Alexa Tudose Alexa2001 Data 5 martie 2015 20:58:26
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <cstdio>
#include <algorithm>
#define pdd pair<double,double>
#define x first
#define y second

using namespace std;

pdd a[120009];
bool ok[120009];
int s[120009],n,dr,p,nr,i;

bool det(pdd a,pdd b,pdd c)
{
    double nr;

     nr=a.x*b.y+b.x*c.y+c.x*a.y;
    nr-=a.x*c.y+b.x*a.y+c.x*b.y;

    if(nr>0) return 1;
    return 0;
}

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

    scanf("%d",&n);

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

    sort(a+1,a+n+1);

    for(i=1;i<=n;++i) ok[i]=0;

    ok[2]=1;dr=1;p=3;nr=2;s[2]=2;s[1]=1;nr=2;

    while(!ok[1])
    {
        while(ok[p])
        {
            p+=dr;
            if(p==n+1)
            {
               p=n-1;
               dr=-1;
            }
        }

        while(nr>=2 && !det(a[s[nr]],a[s[nr-1]],a[p]))
        ok[s[nr--]]=0;

        ok[p]=1;
        s[++nr]=p;
    }

    printf("%d\n",nr-1);

    for(i=nr;i>=1;--i)
    printf("%lf %lf\n",a[s[i]].x,a[s[i]].y);

    return 0;
}