Pagini recente » Cod sursa (job #1135694) | Cod sursa (job #929521) | Cod sursa (job #2764505) | Cod sursa (job #1378684) | Cod sursa (job #1138177)
#include <stdio.h>
#include <stdlib.h>
#define fr(i,a,b) for(int i=a;i<b;++i)
#define N 120000
int n,l;
double x[N],y[N];
int I[N],S[N],s;
int cp(int l,int a,int b){
double x1=x[a]-x[l];
double y1=y[a]-y[l];
double x2=x[b]-x[l];
double y2=y[b]-y[l];
return x1*y2-x2*y1<0?-1:1;
}
int c(const void*a,const void*b){
return cp(l,*(int*)a,*(int*)b);
}
int main(){
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%i",&n);
fr(i,0,n){
scanf("%lf%lf",x+i,y+i);
if(x[i]<x[l])l=i;
I[i]=i;
}
I[I[l]=0]=l;
qsort(I+1,n-1,sizeof(*I),c);
S[s++]=I[0];
S[s++]=I[1];
fr(i,2,n){
while(s>1&&cp(S[s-2],S[s-1],I[i])==1) --s;
S[s++]=I[i];
}
printf("%i\n",s);
fr(i,0,s)printf("%f %f\n",x[S[i]],y[S[i]]);
return 0;
}