Pagini recente » Cod sursa (job #2726291) | Cod sursa (job #1993507) | Cod sursa (job #1389190) | Cod sursa (job #2122268) | Cod sursa (job #1484702)
#include <cstdio>
#include <algorithm>
#define eps 10e-12
#define punct pair<double,double>
#define nmax 120005
#define xx first
#define yy second
using namespace std;
int n,st[nmax],vf,viz[nmax];
punct p[nmax];
void citire()
{
double a,b;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%lf%lf",&a,&b);
p[i]=make_pair(a,b);
}
}
double sarrus(punct p1,punct p2,punct p3)
{
return p1.xx*p2.yy+p2.xx*p3.yy+p3.xx*p1.yy-p1.yy*p2.xx-p2.yy*p3.xx-p3.yy*p1.xx;
}
void rezolv()
{
st[++vf]=1;
st[++vf]=2;
viz[1]=1;
viz[2]=1;
for(int i=3;i<=n;i++)
{
while(viz[i]==0&&sarrus(p[st[vf-1]],p[st[vf]],p[i])<eps)
{
viz[st[vf]]=0;
vf--;
if(vf<2)
break;
}
st[++vf]=i;
viz[i]=1;
}
for(int i=n-1;i>=1;i--)
{
while(viz[i]==0&&sarrus(p[st[vf-1]],p[st[vf]],p[i])<=0)
{
viz[st[vf]]=0;
vf--;
if(vf<2)
break;
}
if(viz[i]==0)
st[++vf]=i,viz[i]=1;;
}
}
void afisare()
{
printf("%d\n",vf);
for(int i=1;i<=vf;i++)
printf("%lf %lf\n",p[st[i]]);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
citire();
sort(p+1,p+n+1);
rezolv();
afisare();
return 0;
}