Pagini recente » Cod sursa (job #945059) | Cod sursa (job #2652208) | Cod sursa (job #2556799) | Cod sursa (job #2391191) | Cod sursa (job #2156318)
#include <bits/stdc++.h>
using namespace std;
struct pt
{
double x,y;
};
pt v[120001],st[120001],v2[120001];
bool cmp(pt a,pt b){
if (a.x<b.x)
return true;
if (a.x==b.x)
if (a.y<b.y)
return true;
return false;
}
bool semnarie (pt p1,pt p2,pt p3) {
return (p2.x*p1.y+p3.x*p2.y+p1.x*p3.y-p1.x*p2.y-p2.x*p3.y-p3.x*p1.y)<0;
}
int main()
{
int n,i,b=0,a;
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w'",stdout);
scanf("%d", &n);
for (i=0;i<n;i++)
scanf("%lf%lf", &v[i].x, &v[i].y);
sort(v,v+n,cmp);
st[++b]=v[0];
for (i=1;i<n;i++) {
while (b>1 && !semnarie(st[b-1],st[b],v[i]))
b--;
st[++b]=v[i];
}
a=b;
for (i=1;i<=b;i++)
v2[i]=st[i];
b=0;
st[++b]=v[n-1];
for (i=n-2;i>=0;i--) {
while (b>1 && !semnarie(st[b-1],st[b],v[i]))
b--;
st[++b]=v[i];
}
for (i=2;i<=b;i++)
v2[i+a-1]=st[i];
a=a+b-2;
printf("%d\n",a);
for(i=1;i<=a;i++)
printf("%lf %lf\n",v2[i].x,v2[i].y);
return 0;
}