Pagini recente » Cod sursa (job #2532445) | Cod sursa (job #845546) | Cod sursa (job #2164498) | Cod sursa (job #1854678) | Cod sursa (job #1344001)
#include <fstream>
#include <cstdio>
#include <algorithm>
#define Nmax 120005
using namespace std;
ofstream g("infasuratoare.out");
long n,i,r[Nmax];
struct Punct{
double x,y;
long poz,uz;
};
Punct v[Nmax];
bool comp(Punct a,Punct b)
{
return a.y<b.y || (a.y==b.y && a.x>b.x);
}
double ad(Punct a,Punct b,Punct p)
{
return a.x*b.y+b.x*p.y+p.x*a.y-p.x*b.y-a.x*p.y-b.x*a.y;
}
bool valid(Punct a,Punct b,Punct c)
{
if (ad(a,b,c)<0)
return 0;
return 1;
}
void infasoara()
{
long stiva[Nmax];
int i=1;
int j=2;
stiva[1]=1;
stiva[2]=2;
i=2;
while (stiva[i]!=n)
{
j++;
while (valid(v[stiva[i-1]],v[stiva[i]],v[j])==0)
i--;
i++;
stiva[i]=j;
}
while (stiva[i]!=1)
{
j--;
while (valid(v[stiva[i-1]],v[stiva[i]],v[j])==0)
i--;
i++;
stiva[i]=j;
}
r[0]=i;
for (j=1;j<=i;j++)
r[j]=stiva[j];
}
int main()
{
freopen("infasuratoare.in","r",stdin);
scanf("%ld",&n);
for (i=1;i<=n;i++)
scanf("%lf%lf",&v[i].x,&v[i].y),v[i].poz=i;
sort(v+1,v+n+1,comp);
infasoara();
r[0]--;
g<<r[0]<<'\n';
for (i=1;i<=r[0];i++)
{
g.precision(6);
g<<fixed<<v[r[i]].x<<' '<<fixed<<v[r[i]].y<<'\n';
}
g.close();
return 0;
}