Pagini recente » Rating raileanu francesca (francesca) | Rating Mendoiu Cosmina (Mendoiu) | Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #3293706)
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream cin ("infasuratoare.in");
ofstream cout ("infasuratoare.out");
const int N = 12e4;
int s[N + 1];
struct point{
double x, y;
}a[N + 1], save;
bool ccw (point a, point b, point c)
{
return ((a.x * b.y + b.x * c.y + a.y * c.x - c.x * b.y - a.x * c.y - a.y * b.x) >= 0);
}
bool cmp (point a, point b)
{
return ccw (save, a, b);
}
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]);
}
a[n] = a[0];
save = a[0];
sort (a + 1, a + n, cmp);
s[0] = 0;
s[1] = 1;
int siz = 2, cat = 1;
while (siz <= n)
{
if (ccw(a[s[cat - 1]], a[s[cat]], a[siz]))
s[++cat] = siz++;
else
--cat;
}
cout << cat << '\n';
for (int i = 0; i < cat; ++i)
cout << fixed << setprecision(12) << a[s[i]].x << ' ' << fixed << setprecision(12) << a[s[i]].y << '\n';
return 0;
}