Pagini recente » Cod sursa (job #1800131) | Cod sursa (job #590342) | Cod sursa (job #1842710) | Borderou de evaluare (job #1330333) | Cod sursa (job #575506)
Cod sursa(job #575506)
#include <stdio.h>
#include <algorithm>
#define Nmax 120002
#define D double
using namespace std;
D x[Nmax],y[Nmax];
int ind[Nmax],St[Nmax];
int N,p;
inline int cmp(int i,int j){
return (y[i]-y[p])*(x[j]-x[p]) > (x[i]-x[p])*(y[j]-y[p]);
}
inline int semn(int i0,int i1,int i2){
return (y[i2]-y[i0])*(x[i1]-x[i0]) >= (x[i2]-x[i0])*(y[i1]-y[i0]);
}
int main(){
int i;
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&N);
for(i=1;i<=N;++i) scanf("%lf%lf",&x[i],&y[i]);
p=1;
for(i=2;i<=N;++i)
if( x[i]<x[p] || (x[i]==x[p] && y[i]<y[p]) )
p=i;
for(i=1;i<=N;++i)
if(i!=p) ind[++ind[0]]=i;
sort(ind+1,ind+N,cmp);
St[St[0]=1]=p;
for(i=1;i<N;++i){
while( St[0]>1 && semn(St[St[0]-1],St[St[0]],ind[i]) )
St[0]--;
St[++St[0]]=ind[i];
}
printf("%d\n",St[0]);
for(i=St[0];i>=1;--i) printf("%lf %lf\n",x[St[i]],y[St[i]]);
fclose(stdin); fclose(stdout);
return 0;
}