Pagini recente » Cod sursa (job #282955) | Cod sursa (job #932871) | Cod sursa (job #937170) | Cod sursa (job #498933) | Cod sursa (job #3285750)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream cin ("infasuratoare.in");
ofstream cout ("infasuratoare.out");
const int N = 12e4;
int s[N + 1];
int n, k;
struct point
{
double x, y;
} a[N + 1];
point fix;
int ccw (point a, point b, point c)
{
return ((a.x * (b.y - c.y) - a.y * (b.x - c.x) + b.x * c.y - b.y * c.x) >= 0);///determinantul de la Aria triunghiului ABC daca e pozitiv atunci A-B-C sunt in ordine trigonometrica
}
bool operator < (const point &a, const point &b)
{
return ccw (fix, a, b);
}
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[k].y)
k = i;
else if (a[i].y == a[k].y && a[i].x < a[k].x)
k = i;
}
swap(a[0], a[k]);
fix = a[0];
sort (a + 1, a + n);
int len = 0, i = 2;
s[len] = 0;
s[++len] = 1;
while (i <= n)
{
if (ccw (a[s[len - 1]], a[s[len]], a[i]) > 0)
s[++len] = i++;
else
--len;
}
cout << len << '\n';
for (int i = 0; i < len; ++i)
cout << fixed << setprecision(12) << a[s[i]].x << ' ' << fixed << setprecision(12) << a[s[i]].y << '\n';
return 0;
}