Pagini recente » Cod sursa (job #653658) | Cod sursa (job #2974469) | Cod sursa (job #2069299) | Cod sursa (job #491409) | Cod sursa (job #1990309)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
struct punct
{
double x, y;
};
const int NMAX = 120021;
punct a[NMAX], O;
int N, M, s[NMAX];
double prod_vec(punct O, punct A, punct B)
{
return (A.x - O.x) * (B.y - O.y) - (B.x - O.x) * (A.y - O.y);
}
int cmp(punct A, punct B)
{
return prod_vec(O, A, B) > 0;
}
int main()
{
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int i, j;
f >> N;
f >> a[1].x >> a[1].y;
O = a[1];
j = 1;
for (i = 2; i <= N; ++i)
{
f >> a[i].x >> a[i].y;
if (a[i].y < O.y || (a[i].y == O.y && a[i].x < O.x))
O = a[i], j = i;
}
swap(a[1], a[j]);
sort(a + 2, a + N + 1, cmp);
M = 2;
s[1] = 1;
s[2] = 2;
for (i = 3; i <= N; ++i)
{
while (M >= 2 && prod_vec(a[s[M]], a[i], a[s[M - 1]]) <= 0) M--;
s[++M] = i;
}
if (prod_vec(a[s[M]], O, a[s[M - 1]]) == 0) --M;
g << M << '\n';
for (i = 1; i <= M; ++i)
g << fixed << setprecision(6) << a[s[i]].x << ' ' << a[s[i]].y << '\n';
return 0;
}