Cod sursa(job #535724)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 17 februarie 2011 18:02:41
Problema Infasuratoare convexa Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
#include<stdio.h>
#define N 120001
typedef struct point
{double x,y;};
long n,i,imax,imin,nsus,njos,j;
point drag[N],jos[N],sus[N],b[N];
double minx,maxx,k;

void mergeSort(point a[N],long p,long q)
{long m=(p+q)>>1,i,j,k,l;
if(p==q)
      return;
mergeSort(a,p,m);
mergeSort(a,m+1,q);
for(i=p,j=m+1,k=p;i<=m||j<=q;)
if(j>q||(i<=m&&(a[i].x<a[j].x||(a[i].x==a[j].x&&a[i].y<a[j].y))))
      b[k++]=a[i++];
else
      b[k++]=a[j++];
for(l=p;l<=q;l++)
      a[l]=b[l];}

double sarrus(point p1,point p2,point p)
{return (p2.x-p1.x)*(p.y-p1.y)-(p.x-p1.x)*(p2.y-p1.y);}

int main()
{freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%ld\n",&n);
for(i=1;i<=n;i++)
      scanf("%lf%lf\n",&drag[i].x,&drag[i].y);
mergeSort(drag,1,n);
nsus=njos=1;
imin=1;
imax=n;
sus[1]=jos[1]=drag[imin];
for(i=2;i<n;i++)
      {k=sarrus(drag[imin],drag[imax],drag[i]);
      if(k<0)
              {jos[++njos]=drag[i];
              while(njos>2&&sarrus(jos[njos-2],jos[njos],jos[njos-1])>0)
                     {jos[njos-1]=jos[njos];
                     njos--;}}
      else
              if(k>0)
                     {sus[++nsus]=drag[i];
                     while(nsus>2&&sarrus(sus[nsus-2],sus[nsus],sus[nsus-1])<0)
                            {sus[nsus-1]=sus[nsus];
                            nsus--;}}}
jos[++njos]=drag[imax];
printf("%ld\n",njos+nsus-1);
for(i=1;i<=njos;i++)
      printf("%.6lf %.6lf\n",jos[i].x,jos[i].y);
for(j=nsus;j>=2;j--)
      printf("%.6lf %.6lf\n",sus[j].x,sus[j].y);
fclose(stdin);
fclose(stdout);
return 0;}