Pagini recente » Cod sursa (job #2482761) | Cod sursa (job #2855531) | Cod sursa (job #582952) | Cod sursa (job #2481229) | Cod sursa (job #2285284)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define pp pair <double, double>
#define x first
#define y second
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
pp p[120010];
int n,i,st[120010];
double determinant(pp a, pp b, pp c)
{
double ans;
ans = a.x*b.y + b.x*c.y + c.x*a.y - a.y*b.x - b.y*c.x - c.y*a.x;
return ans;
}
int main()
{
fin>>n;
for(i=1;i<=n;i++)
{
fin>>p[i].x>>p[i].y;
}
sort(p+1,p+n+1);
st[0]=2; ///varful stivei
st[1]=1;
st[2]=2;
for(i=3;i<=n;i++)
{
while(st[0]>=2 && determinant(p[st[st[0]-1]], p[st[st[0]]], p[i]) > 0)
st[0]--;
st[++st[0]]=i;
}
for(i=n-1;i>=1;i--)
{
while(determinant(p[st[st[0]-1]], p[st[st[0]]], p[i]) > 0)
st[0]--;
st[++st[0]]=i;
}
///for(i=1;i<=st[0]-1;i++)
///cout<<p[st[i]].x<<" "<<p[st[i]].y<<'\n';
fout<<st[0]-1<<'\n';
for(i=st[0]-1;i>=1;i--)
fout<<setprecision(6)<<fixed<<p[st[i]].x<<" "<<p[st[i]].y<<'\n';
return 0;
}