Cod sursa(job #1884233)

Utilizator hegedusPaul Hegedus hegedus Data 18 februarie 2017 15:51:41
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <cstdio>
#define nmax 120001
#define maxim 1000000000
#define minim -1000000000
using namespace std;

int n,i,j,k=1,urmator,v[nmax];
double x,y,p,pj,dx,dy,vx[nmax],vy[nmax],xmin,ymin=maxim;
bool viz[nmax];

void calculare(int i,double panta,bool sens)
{
    urmator=0; viz[i]=1; p=panta;
    for(j=1;j<=n;j++)
        if(!viz[j])
        {
            dy=vy[j]-vy[i];
            dx=vx[j]-vx[i];
            if(dx!=0.f)
            {
                pj=dy/dx;
                if((sens&&pj<p&&pj>0.f)||(!sens&&pj<p))
                    p=pj, urmator=j;
            }
        }

    if(urmator) v[++k]=urmator,calculare(urmator,p,sens);
    else for(j=1;j<=n;j++)
        if(!viz[j])
            if((sens&&vx[j]==vx[i])||(!sens&&vy[j]==vy[i]))
            {v[++k]=j; break;}
}

int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%lf %lf",&vx[i],&vy[i]);
        if(vy[i]<ymin)
            v[1]=i,xmin=vx[i],ymin=vy[i];
        else if(vy[i]==ymin&&vx[i]>xmin) v[1]=i,xmin=vx[i];
    }
    calculare(v[k],maxim,1);
    calculare(v[k],0,0);
    calculare(v[k],maxim,1);
    calculare(v[k],0,0);
    printf("%d\n",k);
    for(i=1;i<=k;i++)
        printf("%.6f %.6f\n",vx[v[i]],vy[v[i]]);
    return 0;
}