Pagini recente » Cod sursa (job #1808251) | Cod sursa (job #573870) | Cod sursa (job #232553) | Cod sursa (job #2108381) | Cod sursa (job #1310463)
#include <cstdio>
#include <algorithm>
#define x first
#define y second
#define nmax 120010
using namespace std;
pair<double,double> a[nmax];
double eps=10e-12;
int st[nmax],vf;
bool viz[nmax];
int n;
void citire()
{
double x,y;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%lf%lf",&x,&y);
a[i]=make_pair(x,y);
}
}
double produs(pair<double,double>&o,pair<double,double>&a,pair<double,double>&b)
{
return (b.x-o.x)*(a.y-o.y)-(a.x-o.x)*(b.y-o.y);
}
void infasuratoare()
{
sort(a+1,a+n+1);
st[1]=1;
st[2]=2;
viz[1]=viz[2]=1;
vf=2;
for(int i=3;i<=n;i++)
{
while(vf>1&&produs(a[st[vf-1]],a[st[vf]],a[i])<eps)
viz[st[vf--]]=0;
st[++vf]=i;
viz[i]=1;
}
for(int i=n;i>=1;i--)
{
if(viz[i]&&i!=1)
continue;
while(vf>1&&produs(a[st[vf-1]],a[st[vf]],a[i])<eps)
viz[st[vf--]]=0;
if(i==1)
continue;
st[++vf]=i;
viz[i]=1;
}
}
void afisare()
{
printf("%d\n",vf);
for(int i=vf;i>=1;i--)
printf("%.6lf %.6lf\n",a[st[i]].x,a[st[i]].y);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
citire();
infasuratoare();
afisare();
return 0;
}