Cod sursa(job #916719)

Utilizator Vladinho97Iordan Vlad Vladinho97 Data 16 martie 2013 20:13:27
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
#define eps 1e-12
using namespace std;
struct punct
{
    double x,y;
};
punct LL,p[120002];
int infasuratoare[120002];
double ccw(punct a,punct b,punct c)
{
    return(b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
bool cmp(punct a,punct b)
{
    if(ccw(LL,a,b)>0)
        return true;
    return false;
}
int main()
{
    punct aux;
    int n,i,top;
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    scanf("%d",&n);
    scanf("%lf%lf",&p[1].x,&p[1].y);
    LL.x=p[1].x;
    LL.y=p[1].y;
    int pozll=1;
    for(i=2;i<=n;i++)
    {
        scanf("%lf%lf",&p[i].x,&p[i].y);
        if((p[i].y<LL.y)||(fabs(p[i].y-LL.y)<eps&&p[i].x<LL.x))
           {
               LL.x=p[i].x;
               LL.y=p[i].y;
               pozll=i;
           }
    }
    aux.x=p[1].x;
    aux.y=p[1].y;
    p[1].x=p[pozll].x;
    p[1].y=p[pozll].y;
    p[pozll].x=aux.x;
    p[pozll].y=aux.y;
    sort(p+2,p+n+1,cmp);
    p[n+1].x=LL.x;
    p[n+1].y=LL.y;
    i=3;
    top=2;
    infasuratoare[1]=1;
    infasuratoare[2]=2;
    while(i<=n)
    {
        if(ccw(p[infasuratoare[top-1]],p[infasuratoare[top]],p[i])>0)
            {
                top++;
                infasuratoare[top]=i;
                i++;
            }
        else
        {
                top--;
        }
    }
    printf("%d\n",top);
    for(i=1;i<=top;i++)
        printf("%.6lf %.6lf\n",p[infasuratoare[i]].x,p[infasuratoare[i]].y);
    return 0;
}