Pagini recente » Cod sursa (job #1281013) | Cod sursa (job #1794203) | Cod sursa (job #2072120) | Cod sursa (job #2404133) | Cod sursa (job #3247471)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
struct vect
{
double x,y;
int p = -2;
}v[120001];
int st[120001],vf=0;
bool cmp(vect a,vect b)
{
if (a.x < b.x)
return 1;
else if (a.x == b.x && a.y < b.y)
return 1;
else
return 0;
}
double functie(vect a, vect b, vect c)
{
return a.x * b.y + b.x * c.y + c.x * a.y - a.y * b.x - b.y * c.x - c.y * a.x;
}
int main()
{
int i,n;
cin>>n;
for(i=1;i<=n;i++)
cin>>v[i].x>>v[i].y;
sort(v+1,v+n+1,cmp);
v[1].p=0;
v[n].p=0;
for(i=2;i<n;i++)
{
double a=functie(v[1],v[n],v[i]);
if(a<0)
v[i].p=-1;
else if(a>0)
v[i].p=1;
else if(a==0)
v[i].p=0;
}
for(i=1;i<=n;i++)
if(v[i].p<=0)
{
if(vf<2)
st[++vf]=i;
else
{
while(vf>=2 && functie(v[st[vf-1]],v[st[vf]],v[i])<0)
vf--;
st[++vf]=i;
}
}
int dx=vf;
for(i=n-1;i>0;i--)
if(v[i].p>=0)
{
if(vf<dx+1)
st[++vf]=i;
else
{
while(vf>=dx+1 && functie(v[st[vf-1]],v[st[vf]],v[i])<0)
vf--;
st[++vf]=i;
}
}
cout<<vf-1<<'\n'<<fixed<<setprecision(6);
for(i=2;i<=vf;i++)
cout<<v[st[i]].x<<' '<<v[st[i]].y<<'\n';
return 0;
}