Cod sursa(job #3315960)

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

using namespace std;

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

struct punct
{
    double x, y;
}v[120001], j[120001], s[120001], st[120001], drum[120001];

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(double ax, double ay, double bx, double by, double cx, double cy)
{
    return (ax * by + bx * cy + cx * ay - cx * by - ax * cy - bx * ay);
}

int main()
{
    int n, i, nj = 0, ns = 0, c = 1;
    in >> n;
    for (i=1;i<=n;i++)
        in >> v[i].x >> v[i].y;
    sort(v, v+n+1, cmp);
    drum[c].x = v[1].x;
    drum[c].y = v[1].y;
    for (i=2;i<n;i++)
    {
        if (arie(v[1].x, v[1].y, v[n].x, v[n].y, v[i].x, v[i].y) < 0)
        {
            nj++;
            j[nj].x = v[i].x;
            j[nj].y = v[i].y;
        }
        else
        {
            ns++;
            s[ns].x = v[i].x;
            s[ns].y = v[i].y;
        }
    }
    int k = 2;
    st[1].x = v[1].x;
    st[1].y = v[1].y;
    st[2].x = j[1].x;
    st[2].y = j[2].y;
    for (i=2;i<=nj;i++)
    {
        while (k<0 && arie(st[k-1].x, st[k-1].y, st[k].x, st[k].y, j[i].x, j[i].y) < 0)
            k--;
        k++;
        st[k].x = j[i].x;
        st[k].y = j[i].y;
    }
    for (i=1;i<=k;i++)
    {
        c++;
        drum[c].x = st[i].x;
        drum[c].y = st[i].y;
    }
    k = 2;
    st[1].x = v[n].x;
    st[1].y = v[n].y;
    st[2].x = s[ns].x;
    st[2].x = s[ns].y;
    for (i=ns-1;i>=1;i--)
    {
        while (k<0 && arie(st[k-1].x, st[k-1].y, st[k].x, st[k].y, s[i].x, s[i].y) > 0)
            k--;
        k++;
        st[k].x = j[i].x;
        st[k].y = j[i].y;
    }
    for (i=1;i<=k;i++)
    {
        c++;
        drum[c].x = st[i].x;
        drum[c].y = st[i].y;
    }
    out << c << "\n";
    for (i=1;i<=c;i++)
        out << drum[c].x << " " << drum[c].y << "\n";
    return 0;
}