Cod sursa(job #3293706)

Utilizator _andrei4567Stan Andrei _andrei4567 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;
}