Pagini recente » Cod sursa (job #2061869) | Cod sursa (job #2938798) | Cod sursa (job #2037762) | Cod sursa (job #2812924) | Cod sursa (job #271909)
Cod sursa(job #271909)
#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;
}