Pagini recente » Cod sursa (job #2744619) | Cod sursa (job #300643) | Cod sursa (job #2638481) | Cod sursa (job #572432) | Cod sursa (job #399433)
Cod sursa(job #399433)
#include<cstdio>
#include<algorithm>
#include<math.h>
#define max 120000
using namespace std;
int N,Pi;
double X[max];
double Y[max];
int I[max];
int S[max];
int cmp( int i1, int i2 ){
return ( (double) (X[i1]-X[Pi])*(Y[i2]-Y[Pi]) < (double) (X[i2]-X[Pi])*(Y[i1]-Y[Pi]));
}
long double semn( int p1, int p2, int p3){
return (long double) X[p1]*Y[p2] + X[p2]*Y[p3] + X[p3]*Y[p1] - Y[p2]*X[p3] - X[p1]*Y[p3] - X[p2]*Y[p1];
}
int main(){
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&N);
int i;
double Px,Py;
Px=Py=1000000001;
for(i=1;i<=N;i++){
scanf("%lf %lf",&X[i],&Y[i]);
if( X[i] < Px || ( X[i] == Px && Y[i] < Py ) ) {
Pi = i;
Py = Y[i];
Px = X[i];
}
}
for(i=1;i<=N;i++){
if( i==Pi ) continue;
I[++I[0]]=i;
}
sort( I + 1 , I + I[0] + 1, cmp);
S[++S[0]] = Pi;
for( i=1;i<=I[0];i++){
if( I[i] == Pi ) continue;
while( S[0]>=2 && semn( S[S[0]-1] , S[S[0]], I[i] ) > 0 ) S[0]--;
S[++S[0]] = I[i];
}
printf("%d\n",S[0]);
S[++S[0]] = Pi;
for(i = S[0]-1; i>1; i-- ) printf("%lf %lf\n",X[S[i]],Y[S[i]]);
printf("%lf %lf\n",Px,Py);
return 0;
}