Cod sursa(job #1691622)

Utilizator Alexa2001Alexa Tudose Alexa2001 Data 18 aprilie 2016 22:34:22
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <cstdio>
#include <algorithm>

using namespace std;

const int NM=120005;

struct Point{double x,y;};
int n,i,st[NM],nr,add;
Point a[NM];
bool ok[NM];
double X,Y;

bool semn(Point a, Point b, Point c)
{
     double d= a.x*b.y+ b.x*c.y+ c.x*a.y;
            d-=a.x*c.y+ b.x*a.y+ c.x*b.y;
     return (d<=0);
}

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

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, cmp);

    st[1]=1;st[2]=2;
    nr=2; ok[2]=1;

    for(i=3, add=1; !ok[1]; i+=add)
    {
        if(i==n) add=-1;
        if(ok[i]) continue;

        while(nr>=2 && semn(a[st[nr]], a[st[nr-1]], a[i])) ok[st[nr--]]=0;
        ok[i]=1;
        st[++nr]=i;
    }
    --nr;
    printf("%d\n", nr);

    for(i=nr; i; --i)
    {
        X=a[st[i]].x, Y=a[st[i]].y;
        printf("%lf %lf\n", X,Y);
    }

    return 0;
}