Pagini recente » Cod sursa (job #2145840) | Cod sursa (job #1009554) | Cod sursa (job #2192714) | Cod sursa (job #531176) | Cod sursa (job #536430)
Cod sursa(job #536430)
#include<stdio.h>
#include<algorithm>
#include<math.h>
#define max 1000000001
#define Nmax 120005
#define er 1e-12
#define f first
#define s second
#define pr pair<double,double>
using namespace std;
int q,k,nr,i,j,m,n;
pr a[Nmax],W[Nmax];
int b[Nmax],ok[Nmax];
int cmp2(double a,double b)
{
if (fabsf(a-b)<er) return 0;
if (a>b) return 1;
return -1;
}
int cmp(const pr a,const pr b)
{
int q=cmp2(a.f,b.f);
if (q!=0) return q==-1;
return cmp2(a.s, b.s)==-1;
}
int semn(pr a,pr b,pr c)
{
return cmp2((a.s-b.s)*c.f+(b.f-a.f)*c.s+(a.f*b.s-b.f*a.s),0);
}
void rezolva()
{
int q=1;
sort(a+1,a+n+1,cmp);
ok[2]=1;
b[1]=1;
b[2]=2;
k = 2;
i = 3;
while (!ok[1])
{
while (ok[i])
{
if (i==n) q=-1;
i+=q;
}
while (k>=2&&semn(a[b[k-1]],a[b[k]],a[i])==-1)
ok[b[k--]]=0;
b[++k]=i;
ok[i]=1;
}
nr=k-1;
for (i=1;i <= nr;++i)
W[i] = a[b[i]];
W[nr+1] = W[1];
}
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].f,&a[i].s);
rezolva();
printf("%d\n",nr);
for (i=1;i<=nr;i++)
printf("%.6lf %.6lf\n",W[i].f,W[i].s);
printf("\n");
return 0;
}