Pagini recente » Cod sursa (job #1726232) | Cod sursa (job #1865664) | Cod sursa (job #1330514) | Cod sursa (job #579076) | Cod sursa (job #2054744)
#include<cstdio>
#include<algorithm>
#define eps 1e-12
using namespace std;
struct punct{double x,y;};
punct v[120001];
int s[120001];
int comp(double a,double b){
if(a+eps<b)
return -1;
else if(b+eps<a)
return 1;
else
return 0;
}
bool cmp(punct a,punct b){
if(comp(a.x,b.x)==-1)
return true;
else if(comp(a.x,b.x)==1)
return false;
else if(comp(a.y,b.y)==-1)
return true;
else
return false;
}
double det(punct a,punct b,punct c){
return a.x*b.y+b.x*c.y+c.x*a.y-c.x*b.y-a.x*c.y-b.x*a.y;
}
int sgn(double a){
return comp(a,0);
}
int main(){
int n,i,top,topsol;
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%lf%lf",&v[i].x,&v[i].y);
sort(v+1,v+n+1,cmp);
s[1]=1;
s[2]=2;
top=2;
for(i=3;i<=n;i++){
while(top>1&&sgn(det(v[s[top-1]],v[s[top]],v[i]))<0&&sgn(det(v[s[top]],v[i],v[s[top-1]]))<0)
top--;
top++;
s[top]=i;
}
topsol=top;
top++;
s[top]=n-1;
for(i=n-2;i>=1;i--){
while(top>topsol&&sgn(det(v[s[top-1]],v[s[top]],v[i]))<0&&sgn(det(v[s[top]],v[i],v[s[top-1]]))<0)
top--;
top++;
s[top]=i;
}
printf("%d\n",top-1);
for(i=1;i<top;i++)
printf("%.6f %.6f\n",v[s[i]].x,v[s[i]].y);
return 0;
}