Pagini recente » Cod sursa (job #171799) | Cod sursa (job #1877399) | Cod sursa (job #1864766) | Cod sursa (job #321519) | Cod sursa (job #1412918)
#include <cstdio>
#include <algorithm>
#define nmax 120005
#define punct pair <double,double>
#define x first
#define y second
using namespace std;
int n,vf;
punct p[nmax];
int st[nmax];
bool viz[nmax];
double eps=10e-12;
double det(punct a,punct b,punct c)
{
return (a.x*b.y+b.x*c.y+c.x*a.y)-(a.y*b.x+b.y*c.x+a.x*c.y);
}
void citire()
{
double ax,ay;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%lf%lf",&ax,&ay);
p[i]=make_pair(ax,ay);
}
}
void rezolv()
{
st[1]=1;
st[2]=2;
vf=2;
viz[1]=viz[2]=1;
for(int i=3;i<=n;i++)
{
while(vf>1&&det(p[st[vf-1]],p[st[vf]],p[i])<eps)
viz[st[vf--]]=0;
viz[i]=1;
st[++vf]=i;
}
for(int i=n-1;i>1;i--)
{
if(viz[i]==0)
{
while(vf>1&&det(p[st[vf-1]],p[st[vf]],p[i])<eps)
viz[st[vf--]]=0;
viz[i]=1;
st[++vf]=i;
}
}
while(vf>1&&det(p[st[vf-1]],p[st[vf]],p[1])<eps)
vf--;
}
void afisare()
{
printf("%d\n",vf);
for(int i=1;i<=vf;i++)
printf("%lf %lf\n",p[st[i]].x,p[st[i]].y);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
citire();
sort(p+1,p+n+1);
rezolv();
afisare();
return 0;
}