Nu aveti permisiuni pentru a descarca fisierul grader_test7.ok
Cod sursa(job #3293706)
Utilizator | Data | 12 aprilie 2025 13:13:35 | |
---|---|---|---|
Problema | Infasuratoare convexa | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 1.15 kb |
#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;
}