Cod sursa(job #3299511)

Utilizator Mihai00700Mihai Ghetu Mihai00700 Data 7 iunie 2025 15:49:04
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.02 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct ura
{
    double x, y;
} v[120002], stiva1[120002], stiva2[120002];
double arie(double xa, double xb, double xc, double ya, double yb, double yc)
{
    /*if ((xa*yb+xb*yc+xc*ya-xc*yb-xa*yc-xb*ya)>=0)
    return true;
    return false;*/
    return xa * yb + xb * yc + xc * ya - xc * yb - xa * yc - xb * ya;
}
bool cmp(ura a, ura b)
{
    if (a.x > b.x)
        return false;
    else
    {
        if (a.x < b.x)
            return true;
        else
        {
            if (a.y < b.y)
                return true;
            else
                return false;
        }
    }
}
int main()
{

    int n;
    f >> n;
    for (int i = 1; i <= n; i++)
        f >> v[i].x >> v[i].y;
    sort(v + 1, v + n + 1, cmp);
    ura st = v[1], dr = v[n];
    int sp1 = 1;
    int h = 0;
    stiva1[1] = st;
    for (int i = 2; i <= n; i++)
    {
        if (arie(st.x, dr.x, v[i].x, st.y, dr.y, v[i].y) < 0 || (v[i].x == dr.x && v[i].y == dr.y) )
        {
            while (sp1 > 1 && arie(stiva1[sp1 - 1].x, stiva1[sp1].x, v[i].x, stiva1[sp1 - 1].y, stiva1[sp1].y, v[i].y) < 0)
            {
                sp1--;
            }
            sp1++;
            stiva1[sp1] = v[i];
        }
    }
    h += sp1 - 1;

    int sp2 = 1;
    stiva2[sp2] = dr;
    for (int i = n - 1; i >= 1; i--)
    {
        if (arie(st.x, dr.x, v[i].x, st.y, dr.y, v[i].y) > 0 || (v[i].x == st.x && v[i].y == st.y))
        {
            while (sp2 > 1 && arie(v[i].x, stiva2[sp2].x, stiva2[sp2 - 1].x, v[i].y, stiva2[sp2].y, stiva2[sp2 - 1].y) > 0)
            {
                sp2--;
            }
            sp2++;
            stiva2[sp2] = v[i];
        }
    }
    h += sp2 - 1;
    g << h << endl;
    g << setprecision(6) << fixed;

    for (int i = 1; i < sp1; i++)
        g << stiva1[i].x << " " << stiva1[i].y << endl;
    for (int i = 1; i < sp2; i++)
        g << stiva2[i].x << " " << stiva2[i].y << endl;
    return 0;
}