Cod sursa(job #271909)

Utilizator zbarniZajzon Barna zbarni Data 6 martie 2009 02:15:08
Problema Infasuratoare convexa Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 2.08 kb
#include<stdio.h>
#define nx 120500
#define inf 1000000001
struct asd
 {
  double x,y;
 };
asd a[nx];
int v[nx];
int n,p;

int cmp (int x,int y,int z)
 {
  double s=((a[x].x-a[z].x)*(a[y].y-a[z].y)-(a[x].y-a[z].y)*(a[y].x-a[z].x));
  if (s>0) return 1;
  if (s<0) return -1;
  return 0;
 }

void sort (int st,int dr)
 {
  int i=st,j=dr,r=(st+dr)/2;
  asd s;
  do {
   while (cmp(1,i,r)==1) ++i;
   while (cmp(1,r,j)==1) --j;
   if (i<=j) {
     s=a[i];
     a[i]=a[j];
     a[j]=s;
     i++,--j;
   }
  } while (i<=j);
  if (st<j) sort(st,j);
  if (i<dr) sort(i,dr);
 }
/*int cmp(asd A,asd B,asd C)
{
    double semn=((A.x-C.x)*(B.y-C.y)-(A.y-C.y)*(B.x-C.x));
    if(semn>0) return 1;
    if(semn<0) return -1;
    return 0;
}

void sort(int st,int dr)
{
    int i=st,j=dr;
    asd elem=a[(i+j)/2],aux;
    do
	{
	    while(cmp(a[1],a[i],elem) == 1) ++i;
	    while(cmp(a[1],elem,a[j]) == 1) --j;
	    if(i<=j)
		{
		    aux=a[i];
		    a[i]=a[j];
		    a[j]=aux;
		    ++i;
		    --j;
		}
	}while(i<=j);
    if(st<j)   sort(st,j);
    if(i<dr)   sort(i,dr);
} */

int main()
 {
  freopen ("infasuratoare.in","r",stdin);
  freopen ("infasuratoare.out","w",stdout);
  int n,i;
  double miny=inf;
  double minx=inf;
  scanf("%d",&n);
  for (i=1;i<=n;++i) {
    scanf("%lf%lf",&a[i].x,&a[i].y);
 /*   if (a[i].y<a[p].y || (a[i].y==a[p].y && a[i].x<a[p].x))
      p=i;*/
   if(a[i].y<miny)
		{
		    miny=a[i].y;
		    minx=a[i].x;
		    a[0]=a[i];
		    a[i]=a[1];
		    a[1]=a[0];
		}
	    else
                if(a[i].y==miny)   
                    if(a[i].x<minx)   
                        {   
                            minx=a[i].x;   
			    a[0]=a[i];
                            a[i]=a[1];   
                            a[1]=a[0];   
			}
	}

//  a[0]=a[p],a[p]=a[1],a[1]=a[0];
  sort(2,n);
  int vf=1;
  v[vf]=1;
  for (i=2;i<=n;++i)
   {
    while (vf>1 && cmp(v[vf-1],v[vf],i)==-1) --vf;
    v[++vf]=i;
   }
  printf("%d\n",vf);
  for (i=1;i<=vf;++i)
   printf ("%.6f %.6f\n",a[v[i]].x,a[v[i]].y);
  return 0;
 }