Pagini recente » Cod sursa (job #917484) | Cod sursa (job #2675158) | Cod sursa (job #1485616) | Cod sursa (job #1578432) | Cod sursa (job #411932)
Cod sursa(job #411932)
#include <stdio.h>
#include <algorithm>
#define Nmax 120005
#define INF 2147000000
#define ld long double
#define d double
using namespace std;
double x[Nmax],y[Nmax];
int ind[Nmax],st[Nmax],n,i,p;
int cmp(int i,int j){
return( (d)(x[i]-x[p])*(y[j]-y[p]) < (d)(x[j]-x[p])*(y[i]-y[p]) );
}
ld semn(int i1,int i2,int i3){
return (ld) (x[i2]-x[i1])*(y[i3]-y[i1]) - (x[i3]-x[i1])*(y[i2]-y[i1]);
}
int main(){
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
x[p=0]=y[0]=INF;
for(i=1;i<=n;++i){
scanf("%lf%lf",&x[i],&y[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+ind[0]+1,cmp);
st[st[0]=1]=p;
for(i=1;i<=ind[0];++i){
if( st[0]>1 && semn(st[st[0]-1],st[st[0]],ind[i])>0)
st[0]--;
st[++st[0]]=ind[i];
}
printf("%d\n",st[0]);
reverse(st+1,st+st[0]+1);
for(i=1;i<=st[0];++i) printf("%lf %lf\n",x[st[i]],y[st[i]]);
fclose(stdin); fclose(stdout);
return 0;
}