Pagini recente » Cod sursa (job #638499) | Cod sursa (job #2585065) | Cod sursa (job #106648) | Cod sursa (job #1147934) | Cod sursa (job #886752)
Cod sursa(job #886752)
#include<stdio.h>
#include<algorithm>
using namespace std;
#define esp 1e-12
#define max_n 120001
struct punct{double x,y;};
punct v[max_n];
int ok[max_n],s[max_n];
int n,h;
/*
int cmp1(double a,double b){
if(a+esp<b) return 1;
if(b+esp<a) return -1;
return 0;
}
bool cmp(const punct &a,const punct &b){
int t=cmp1(a.x,b.x);
if(t!=0) return t==1;
return (cmp1(a.y,b.y)==1);
}*/
int compar(punct a,punct b){
return a.x<b.x || a.x<b.x && a.y<b.y;
}
int semn(punct o,punct a,punct b){
return (a.x-o.x)*(b.y-o.y) - (b.x-o.x)*(a.y-o.y);
}
void convex(){
sort(v+1,v+n+1,compar);
int k=2,q,i=3;
s[1]=1;s[2]=2;
ok[2]=1;
q=1;
while(!ok[1]){
while(ok[i]){
if(i==n) q=-1;
i+=q;
}
while(k>=2 && semn(v[s[k-1]],v[s[k]],v[i])<esp)
ok[s[k--]]=0;
s[++k]=i;
ok[i]=1;
}
h=k-1;
}
int main (){
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lf %lf",&v[i].x,&v[i].y);
convex();
printf("%d\n",h);
for(int i=2;i<=h+1;i++)
printf("%lf %lf\n",v[s[i]].x,v[s[i]].y);
return 0;
}