Pagini recente » Cod sursa (job #2671853) | Istoria paginii info-oltenia-2018/echipe/9-10 | Cod sursa (job #239546) | Info Oltenia 2018 Proba pe Echipe Clasele 9 - 10 | Cod sursa (job #1773263)
#include <stdio.h>
#include <algorithm>
using namespace std;
struct punct
{
double x,y;
};
punct a[120009];
int st[120009],n,m,i,j,k;
int sgn(punct * a,punct * b,punct * c)
{
return (a->x*b->y+a->y*c->x+b->x*c->y-c->x*b->y-b->x*a->y-a->x*c->y < 0);
}
int cmp(const punct &a,const punct & b)
{
if (a.x==b.x)
return (a.y<b.y);
return (a.x<b.x);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for (i=0;i<n;++i)
scanf("%lf%lf",&a[i].x,&a[i].y);
//qsort(a,n,sizeof(punct),cmp);
sort(a,a+n,cmp);
k=1;
st[k]=0;
st[++k]=1;
for (i=2;i<n;++i)
{
while (k>1 && sgn(&a[st[k-1]],&a[st[k]],&a[i]))
k--;
st[++k]=i;
}
for (i=n-2;i>=0;--i)
{
while (k>1 && sgn(&a[st[k-1]],&a[st[k]],&a[i]))
k--;
st[++k]=i;
}
printf("%d\n",k);
for (i=1;i<k;++i)
printf("%.7lf %.7lf\n",a[st[i]].x,a[st[i]].y);
puts("");
fclose(stdin);
fclose(stdout);
return 0;
}