Pagini recente » Cod sursa (job #239123) | Cod sursa (job #1389923) | Cod sursa (job #2249695) | Cod sursa (job #2787896) | Cod sursa (job #2552416)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <iomanip>
using namespace std;
int n;
struct Punct
{
double x,y;
}v[120005];
bool cmp(Punct a, Punct b)
{
if(a.x>b.x)
return false;
else if(a.x<b.x)
return true;
else if(a.y>b.y)
return false;
return true;
}
Punct stjos[120005],stsus[120005];
double arie(Punct a, Punct b, Punct c)
{
/// x1 y1 1 ///a
/// x2 y2 1 ///b
/// x3 y3 1 ///c
double arie=a.x*(b.y-c.y)-b.x*(a.y-c.y)+c.x*(a.y-b.y);
return arie;
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
cin>>n;
int i,vfjos,vfsus;
for(i=1;i<=n;i++)
cin>>v[i].x>>v[i].y;
sort(v+1,v+n+1,cmp);
stjos[1]=v[1];
vfjos=1;
stsus[1]=v[1];
vfsus=1;
for(i=2;i<=n;i++){
if(arie(v[1],v[n],v[i])<=0)///jos
{
while(vfjos>1 && arie(stjos[vfjos-1],stjos[vfjos],v[i])<0)
vfjos--;
stjos[++vfjos]=v[i];
}
if(arie(v[1],v[n],v[i])>=0)
{
while(vfsus>1 && arie(stsus[vfsus-1],stsus[vfsus],v[i])>0)
vfsus--;
stsus[++vfsus]=v[i];
}
}
cout<<vfjos+vfsus-2<<'\n';
for(i=2;i<=vfjos;i++)
cout<<fixed<<setprecision(6)<<stjos[i].x<<' '<<stjos[i].y<<'\n';
for(i=vfsus-1;i>=2;i--)
cout<<fixed<<setprecision(6)<<stsus[i].x<<' '<<stsus[i].y<<'\n';
cout<<fixed<<setprecision(6)<<stjos[1].x<<' '<<stjos[1].y;
return 0;
}