Pagini recente » Cod sursa (job #883332) | Cod sursa (job #1764802) | Cod sursa (job #784739) | Cod sursa (job #1591849) | Cod sursa (job #1597635)
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#define NMAX 120005
#define eps 0.000000000001
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int i, n, m = 0;
struct punct
{
double x, y, panta;
}v[NMAX], stiva[NMAX];
double det(punct a, punct b, punct c)
{
return a.x * b.y + b.x * c.y + c.x * a.y - b.y * c.x - a.y * b.x - a.x * c.y;
}
bool cmp(punct a, punct b)
{
return det(v[1], a, b) < 0;
}
bool cmp2(punct a, punct b)
{
if (fabs(a.x - b.x) < eps)
return a.y < b.y;
return a.x < b.x;
}
int main()
{
f >> n;
for (i = 1; i <= n; ++ i)
f >> v[i].x >> v[i].y;
sort(v + 1, v + n + 1, cmp2);
sort(v + 2, v + n + 1, cmp);
stiva[++ m] = v[1];
stiva[++ m] = v[2];
for (i = 3; i <= n; ++ i)
{
while (m >= 3 && det(stiva[m], stiva[m - 1], v[i]) < 0)
m --;
stiva[++ m] = v[i];
}
g << m << '\n';
g << fixed << setprecision(12);
for (i = m; i >= 1; -- i)
g << stiva[i].x << " " << stiva[i].y << '\n';
return 0;
}