Pagini recente » Cod sursa (job #279174) | Cod sursa (job #328185) | Cod sursa (job #2869906) | Cod sursa (job #2078526) | Cod sursa (job #3214825)
#include <fstream>
#include <algorithm>
#include <stack>
#include <iomanip>
#define double long double
using namespace std;
ifstream cin ("infasuratoare.in");
ofstream cout ("infasuratoare.out");
const int N = 12e4;
int s[N + 1];
int n;
struct point
{
double x, y;
} a[N + 1], saved;
int det (point a, point b, point c)
{
return (a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y) > 0);
}
bool operator < (const point &a, const point &b)
{
return det (saved, a, b);
}
int main()
{
cin >> n;
cin >> 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[i], a[0]);
}
saved = a[0];
a[n] = a[0];
sort (a + 1, a + n);
int len = 0, i = 2;
s[len] = 0;
s[++len] = 1;
while (i <= n)
{
if (det (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;
}