Pagini recente » Cod sursa (job #2200978) | Cod sursa (job #2522006) | Cod sursa (job #1360754) | Cod sursa (job #2590204) | Cod sursa (job #2897236)
#include <fstream>
#include <algorithm>
#include <math.h>
#include <iomanip>
using namespace std;
ifstream cin ("infasuratoare.in");
ofstream cout ("infasuratoare.out");
const int N = 12e4;
int h[N + 2];
struct da
{
double x, y;
} a[N + 2];
int ccw (da a, da b, da c)
{
double ga = (b.x - a.x) * (c.y - b.y) - (b.y - a.y) * (c.x - b.x);
if (ga == 0)
return 0;
if (ga > 0)
return 1;
return -1;
}
bool cmp (da b, da c)
{
return ccw(a[0], b, c) > 0;
}
int n;
int main()
{
cin >> n >> a[0].x >> a[0].y;
for (int i = 1; i < n; ++i)
{
cin >> a[i].x >> a[i].y;
if (a[i].y < a[0].y || (a[i].y == a[0].y && a[i].x < a[0].x))
swap(a[0], a[i]);
}
sort (a + 1, a + n, cmp);
a[n] = a[0];
int i = 2, top = 1;
h[0] = 0;
h[1] = 1;
while (i <= n)
{
if (ccw(a[h[top - 1]], a[h[top]], a[i]) > 0)
{
h[++top] = i;
++i;
}
else
--top;
}
cout << top << '\n';
for (int i = 0; i < top; ++i)
{
cout << fixed << setprecision(6) << a[h[i]].x << ' ' << fixed << setprecision(7) << a[h[i]].y << '\n';
}
return 0;
}