Pagini recente » Cod sursa (job #272012) | Cod sursa (job #404090) | Cod sursa (job #2366093) | Cod sursa (job #163596) | Cod sursa (job #2284400)
#include <iostream>
#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, 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 - b.y*c.x - c.y*a.x - a.y*b.x;
return ans;
}
int main()
{
int i;
fin >> n;
for(i=1; i<=n; i++)
{
fin >> p[i].x >> p[i].y;
}
sort(p+1, p+n+1);
st[1] = 1;
st[2] = 2;
st[0] = 2;
for(i=3; i<=n; i++)
{
while( st[0]>1 && 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;
}
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;
fout << '\n';
}
return 0;
}