Pagini recente » Cod sursa (job #2882206) | Cod sursa (job #78759) | Cod sursa (job #2098174) | Cod sursa (job #501765) | Cod sursa (job #2809943)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n,viz[120001],st[120001],nr;
double a,b;
struct imp
{
double a,b;
};
imp afis[120001];
bool cmp(imp x,imp y)
{
if (x.a>y.a)
return 0;
else if (x.a==y.a)
{
if (x.b>y.b)
return 0;
else return 1;
}
else return 1;
}
imp v[120001];
double dir (imp x,imp y,imp z)
{
return (y.a-x.a)*(z.b-x.b)-(y.b-x.b)*(z.a-x.a);
}
int main()
{
f>>n;
for (int i=1; i<=n; i++)
{
f>>v[i].a>>v[i].b;
//cout<<v[i].a<<' '<<v[i].b<<'\n';
}
sort(v+1,v+1+n,cmp);
for (int i=1; i<=n; i++)
{
// cout<<v[i].a<<' '<<v[i].b<<'\n';
//cout<<v[i].a<<' '<<v[i].b<<'\n';
}
st[1]=1;
st[2]=2;
viz[2]=1;
nr=2;
for (int i=1,p=1; i>0; i+=(p=(i==n ? -p : p)))
{
if (viz[i]==0)
{
while (nr>=2 && dir(v[st[nr-1]],v[st[nr]],v[i])<=0)
{
//cout<<i<<' '<<nr<<'\n';
viz[st[nr]]=0;
nr--;
}
nr++;
st[nr]=i;
viz[i]=1;
}
}
g<<setprecision(6)<<fixed;
g<<nr-1<<'\n';
for (int i=1; i<nr; i++)
{
g<<v[st[i]].a<<' '<<v[st[i]].b<<'\n';
}
return 0;
}