Cod sursa(job #3316021)

Utilizator hiAvidMihaly David-Gabriel hiAvid Data 16 octombrie 2025 21:37:35
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");

struct punct
{
    double x, y;
    int p;
} v[10];

bool cmp(punct a, punct b)
{
    if (a.x < b.x)
        return true;
    else if (a.x > b.x)
        return false;
    else if (a.y < b.y)
        return true;
    else
        return false;
}

double arie(punct a, punct b, punct c)
{
    return (a.x * b.y + b.x * c.y + c.x * a.y - c.x * b.y - a.x * c.y - b.x * a.y);
}

int main()
{
    int n, i;
    in >> n;
    for (i = 1; i <= n; i++)
        in >> v[i].x >> v[i].y;
    sort(v + 1, v + n + 1, cmp);
    for (i = 2; i < n; i++)
    {
        if (arie(v[1], v[n], v[i]) < 0)
            v[i].p = 1;
        else
            v[i].p = 2;
    }
    int st[10], k = 1;
    st[1] = 1;
    for (i = 2; i <= n; i++)
    {
        if (v[i].p == 1 || v[i].p == 0)
        {
            while (k > 1 && arie(v[st[k - 1]], v[st[k]], v[i]) < 0)
                k--;
            k++;
            st[k] = i;
        }
    }
    int ck = k;
    st[k] = n;
    for (i = n - 1; i >= 1; i--)
    {
        if (v[i].p == 2 || v[i].p == 0)
        {
            while (k > ck && arie(v[st[k - 1]], v[st[k]], v[i]) < 0)
                k--;
            k++;
            st[k] = i;
        }
    }
    out << k - 1 << "\n";
    for (i = 2; i <= k; i++)
        out << fixed << setprecision(6) << v[st[i]].x << " " << v[st[i]].y << "\n";
    return 0;
}