Pagini recente » Cod sursa (job #2649251) | Cod sursa (job #2472028) | Cod sursa (job #3120842) | Cod sursa (job #1378165) | Cod sursa (job #2047776)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
int nr, i, k;
struct nod
{
double x, y;
}v[122005],st[122005];
bool cr1(nod a, nod b)
{
if(a.x != b.x)
return a.x < b.x;
return a.y < b.y;
}
double det(nod a, nod b, nod c)
{
return a.x * b.y + b.x * c.y + c.x * a.y - c.x * b.y - b.x * a.y - a.x * c.y;
}
bool cr2(nod a, nod b)
{
return det(v[1], a, b) < 0;
}
int main()
{
cin >> nr;
for(i=1; i <= nr; i++)
{
cin >> v[i].x >> v[i].y;
}
sort(v+1, v+nr+1, cr1);
sort(v+2, v+nr+1, cr2);
st[1] = v[1];
st[2] = v[2];
st[3] = v[3];
k = 3;
for(i=4; i <= nr; i++)
{
while((k >= 3) && (det(st[k-1], st[k], v[i]) > 0))
k--;
k++;
st[k] = v[i];
}
cout << k << '\n';
cout<<fixed<<setprecision(12);
for(i=k; i > 0; i--)
{
cout << st[i].x << ' ' << st[i].y << '\n';
}
}