Pagini recente » Cod sursa (job #1369827) | Cod sursa (job #2895052) | Cod sursa (job #1585634) | Cod sursa (job #3121048) | Cod sursa (job #2666019)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
#define dbl double
struct ura{
dbl x,y;
int tip;
};
ura v[120001];
int st[120001];
int st2[120001];
bool cmp(ura a,ura b)
{
if(a.y!=b.y)
return (a.y<b.y);
else
return (a.x<b.x);
}
int arie(dbl x1,dbl y1,dbl x2,dbl y2,dbl x3,dbl y3)
{
return x1*y2+x2*y3+x3*y1-(y1*x2+y2*x3+y3*x1);
}
int main()
{
int n,i,nr,nr2;
cin>>n;
for(i=1;i<=n;i++)
{
cin>>v[i].x>>v[i].y;
}
sort(v+1,v+n+1,cmp);
v[1].tip=-1;
v[n].tip=1;
for(i=2;i<n;i++)
{
if(arie(v[1].x,v[1].y,v[n].x,v[n].y,v[i].x,v[i].y)<0)//stanga
v[i].tip=1;
else
v[i].tip=-1;
}
nr=1;
st[nr]=1;
for(i=2;i<n;i++)
{
if(v[i].tip==1)
{
if(nr>1 && arie(v[st[nr-1]].x,v[st[nr-1]].y,v[st[nr]].x,v[st[nr]].y,v[i].x,v[i].y)*v[i].tip<0)
st[nr]=i;
else
{
nr++;
st[nr]=i;
}
}
}
nr2=1;
st2[nr2]=n;
for(i=n-1;i>1;i--)
{
if(v[i].tip==-1)
{
if(nr2>1 && arie(v[st2[nr2-1]].x,v[st2[nr2-1]].y,v[st2[nr2]].x,v[st2[nr2]].y,v[i].x,v[i].y)*v[i].tip>0)
st2[nr2]=i;
else
{
nr2++;
st2[nr2]=i;
}
}
}
cout<<nr+nr2<<'\n';
for(i=1;i<=nr;i++)
cout<<v[st[i]].x<<" "<<v[st[i]].y<<'\n';
for(i=1;i<=nr2;i++)
cout<<v[st2[i]].x<<" "<<v[st2[i]].y<<'\n';
return 0;
}