Pagini recente » Cod sursa (job #1751183) | Cod sursa (job #1819465) | Cod sursa (job #434652) | Cod sursa (job #1154581) | Cod sursa (job #1647811)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
#define eps 1e-12
#define p pair<double, double>
#define x first
#define y second
#define MAX 120100
double cross_product(p a, p b, p c)
{
return a.x * b.y + b.x * c.y + c.x * a.y - b.y * c.x - c.y * a.x - a.y * b.x;
}
p a[MAX];
int st[MAX], viz[MAX];
int main()
{
int n, i, dr;
fin >> n;
for(i = 1 ; i <= n ; i++)
{
fin >> a[i].first >> a[i].second;
}
sort(a + 1, a + n + 1);
dr = 0;
st[++dr] = 1;
st[++dr] = 2;
viz[1] = viz[2] = 1;
for(i = 3 ; i <= n ; i++)
{
while(dr >= 2 && cross_product(a[st[dr - 1]], a[st[dr]], a[i]) < eps)
{
viz[st[dr--]] = 0;
}
st[++dr] = i;
viz[st[dr]] = 1;
}
for(i = n ; i >= 1 ; i--)
{
if(!viz[i])
{
while(dr >= 2 && cross_product(a[st[dr - 1]], a[st[dr]], a[i]) < eps)
{
viz[st[dr--]] = 0;
}
st[++dr] = i;
viz[st[dr]] = 1;
}
}
fout << dr << "\n";
fout << fixed << setprecision(6);
for(i = 1 ; i <= dr ; i ++)
{
fout << a[st[i]].first << " " << a[st[i]].second << "\n";
}
}