Pagini recente » Cod sursa (job #1210513) | Cod sursa (job #1271525) | Cod sursa (job #2569182) | Cod sursa (job #2840115) | Cod sursa (job #2878501)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
int st[120001],h[20],rez[120001];
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
struct ura
{
double x,y;
int o;
}p[120001],p1[120001],p2[120001];
void schimb(ura &a, ura b)
{
a.x=b.x;
a.y=b.y;
a.o=b.o;
}
int arie(ura a, ura b, ura c)
{
return (a.x*b.y+b.x*c.y+c.x*a.y-b.y*c.x-c.y*a.x-a.y*b.x);
}
bool cmp( ura a, ura b)
{
if(a.y<b.y)
return true;
if(a.y>b.y)
return false;
if(a.x<b.x)
return true;
return false;
}
int main()
{
int n,i,k1=1,k2=1,k,ok;
double a;
cin>>n;
for(i=1;i<=n;i++)
cin>>p[i].x>>p[i].y;
sort(p+1,p+n+1,cmp);
p[1].o=1;
p[n].o=n;
schimb(p2[1],p[1]);
schimb(p1[1],p[1]);
for(i=2;i<n;i++)
{
a=arie(p[1],p[n],p[i]);
p[i].o=i;
if(a<0)///punctul se afla la dreapta
{
k2++;
schimb(p2[k2],p[i]);
}
else
{
k1++;
schimb(p1[k1],p[i]);
}
}
k2++;
k1++;
schimb(p2[k2],p[n]);
schimb(p1[k1],p[n]);
st[1]=1;
st[2]=2;
k=2;
for(i=3;i<=k2;i++)
{
ok=0;
while(k>=2&&ok==0)
{
a=arie(p2[st[k-1]],p2[st[k]],p2[i]);
if(a>0)
ok=1;
else
k--;
}
k++;
st[k]=i;
}
for(i=1;i<=k;i++)
rez[i]=p2[st[i]].o;
int f=k;
st[1]=1;
st[2]=2;
k=2;
for(i=3;i<=k1;i++)
{
ok=0;
while(k>=2&&ok==0)
{
a=arie(p1[st[k-1]],p1[st[k]],p1[i]);
if(a<0)
ok=1;
else
k--;
}
k++;
st[k]=i;
}
for(i=2;i<k;i++)
rez[k+f-i]=p1[st[i]].o;
f+=k-2;
cout<<f<<'\n';
for(i=1;i<=f;i++)
cout<<fixed<<setprecision(6)<<p[rez[i]].x<<" "<<p[rez[i]].y<<'\n';
return 0;
}