Pagini recente » Cod sursa (job #157151) | Cod sursa (job #589699) | Cod sursa (job #2447528) | Cod sursa (job #2653480) | Cod sursa (job #1671472)
#include <cstdio>
#include <algorithm>
using namespace std;
struct z
{
double x,y;
}v[120001];
double X,Y;
int stiva[120001];
bool comp(z p1,z p2)
{
return (p1.y-Y)*(p2.x-X)>(p2.y-Y)*(p1.x-X);
}
int main()
{
int n,p,i,vf,min;
double eps,aux;
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
eps=0.000000000000;
scanf("%d",&n);
min=1000000000;
p=0;
for(i=1; i<=n; i++){
scanf("%lf%lf",&v[i].x,&v[i].y);
if(min>v[i].x)
min=v[i].x,p=i;
}
aux=v[1].x;
v[1].x=v[p].x;
v[p].x=aux;
aux=v[1].y;
v[1].y=v[p].y;
v[p].y=aux;
X=v[1].x;
Y=v[1].y;
sort(v+2,v+1+n,comp);
stiva[1]=1;
stiva[2]=2;
stiva[3]=3;
vf=3;
for(i=4; i<=n; i++){
while(vf>2 && (v[stiva[vf]].y-v[stiva[vf-1]].y)*(v[i].x-v[stiva[vf-1]].x)<(v[i].y-v[stiva[vf-1]].y)*(v[stiva[vf]].x-v[stiva[vf-1]].x))
vf--;
stiva[++vf]=i;
}
printf("%d\n",vf);
for(i=vf; i>0; i--)
printf("%lf %lf\n",v[stiva[i]].x,v[stiva[i]].y);
return 0;
}