Pagini recente » Cod sursa (job #1169060) | Cod sursa (job #2238492) | Cod sursa (job #723789) | Cod sursa (job #1996205) | Cod sursa (job #1297282)
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int n,i,j,p,nr;
struct punct
{
double x;
double y;
}q,cp,v[120005],w[120005];
double sp(const punct a,const punct b,const punct c)
{
return ((b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x));
}
double cmp(const punct a,const punct b)
{
return sp(v[1],a,b)>0;
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
p=1;
for (i=1;i<=n;i++)
{
scanf("%lf %lf",&v[i].x,&v[i].y);
if (v[i].x<v[p].x) p=i; else
if ((v[i].x==v[p].x)&&(v[i].y<v[p].y)) p=i;
}
q=v[p]; punct aux;
aux=v[p]; v[p]=v[1]; v[1]=aux;
sort(v+2,v+n+1,cmp);
nr=2; w[1]=v[1]; w[2]=v[2];
for (i=3;i<=n;i++)
{
while ((nr>1)&&(sp(w[nr],w[nr-1],v[i])>0)) nr--;
w[++nr]=v[i];
}
printf("%d\n",nr);
sort(w+1,w+nr+1,cmp);
for (i=1;i<=nr;i++) printf("%.12lf %.12lf\n",w[i].x,w[i].y);
return 0;
}