Pagini recente » Cod sursa (job #2493245) | Cod sursa (job #1180215) | Cod sursa (job #1401485) | Cod sursa (job #1072379) | Cod sursa (job #2304083)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream cin ("infasuratoare.in");
ofstream cout ("infasuratoare.out");
struct ura
{
double a,b;
int poz;
}v[120003],rez[120003];
double triunghi (int pz1, int pz2, int pz3)
{
double x1=v[pz1].a,x2=v[pz2].a,x3=v[pz3].a,y1=v[pz1].b,y2=v[pz2].b,y3=v[pz3].b;
double rez = (x1-x2)*(y1-y3)-(x1-x3)*(y1-y2);
return rez;
}
int st[120003];
bool cmp (ura a, ura b)
{
if(a.a<b.a)
return true;
if(a.a>b.a)
return false;
if(a.b<b.b)
return true;
return false;
}
int main()
{
int n,i,j,k,rezz=0;
cin>>n;
for(i=1;i<=n;++i)
{
cin>>v[i].a>>v[i].b;
v[i].poz=i;
}
sort(v+1,v+n+1,cmp);
for(i=1;i<=n;++i)
{
rez[i].a=v[i].a;
rez[i].b=v[i].b;
}
k=0;
st[++k]=1;
st[++k]=2;
for(i=3;i<=n;++i)
{
while(k>1 && triunghi(st[k-1],st[k],i)<0)
--k;
st[++k]=i;
}
for(i=1;i<=k;++i)
{
rez[++rezz].a=v[st[i]].a;
rez[rezz].b=v[st[i]].b;
}
k=0;
st[++k]=n;
st[++k]=n-1;
for(i=n-2;i>=1;--i)
{
while(k>1 && triunghi(st[k-1],st[k],i)<0)
--k;
st[++k]=i;
}
for(i=2;i<k;++i)
{
rez[++rezz].a=v[st[i]].a;
rez[rezz].b=v[st[i]].b;
}
cout<<rezz<<'\n';
for(i=1;i<=rezz;++i)
cout<<rez[i].a<<' '<<rez[i].b<<'\n';
return 0;
}