Pagini recente » Cod sursa (job #1412487) | Cod sursa (job #1081981) | Cod sursa (job #2096277) | Cod sursa (job #2666894) | Cod sursa (job #1377272)
#include <cstdio>
#include <algorithm>
#define pdd pair<double,double>
#define x first
#define y second
using namespace std;
pdd a[120009];
bool ok[120009];
int s[120009],n,dr,p,nr,i;
bool det(pdd a,pdd b,pdd c)
{
double nr;
nr=a.x*b.y+b.x*c.y+c.x*a.y;
nr-=a.x*c.y+b.x*a.y+c.x*b.y;
if(nr>0) return 1;
return 0;
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;++i)
scanf("%lf%lf",&a[i].x,&a[i].y);
sort(a+1,a+n+1);
for(i=1;i<=n;++i) ok[i]=0;
ok[2]=1;dr=1;p=3;nr=2;s[2]=2;s[1]=1;nr=2;
while(!ok[1])
{
while(ok[p])
{
p+=dr;
if(p==n+1)
{
p=n-1;
dr=-1;
}
}
while(nr>=2 && !det(a[s[nr]],a[s[nr-1]],a[p]))
ok[s[nr--]]=0;
ok[p]=1;
s[++nr]=p;
}
printf("%d\n",nr-1);
for(i=nr;i>=1;--i)
printf("%lf %lf\n",a[s[i]].x,a[s[i]].y);
return 0;
}