Cod sursa(job #2868873)

Utilizator andu9andu nita andu9 Data 11 martie 2022 11:13:41
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.67 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#include <iomanip>

using namespace std;

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

struct point
{
    double x, y;
};

int indice;
stack <point> stiva;
vector <point> v, res;

bool stanga (point p0, point p1, point p2) // punctul p0 in functie de dreapta determinata de pucntele p1 si p2
{
    double det;
    det = (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
    if (det > 0)
        return 1;
    return 0;
}

bool cond (point a, point b)
{
    if (stanga (v[indice], a, b))
        return 1;
    return 0;
}

int main ()
{
    point x;
    int n, i;
    f >> n, v.resize (n + 1);
    for (i = 1; i <= n; i += 1)
        f >> v[i].x >> v[i].y;
    indice = 1;
    for (i = 2; i <= n; i += 1)
    {
        if (v[i].y < v[indice].y or (v[i].y == v[indice].y and v[i].x < v[indice].x))
            indice = i;
    }
    swap (v[1], v[indice]);
    sort (v.begin () + 2, v.end (), cond);
    stiva.push (v[1]), stiva.push (v[2]);
    for (i = 3; i <= n; i += 1)
    {
        x = stiva.top (), stiva.pop ();
        while (!stanga (stiva.top (), x, v[i]))
            x = stiva.top (), stiva.pop ();
        stiva.push (x), stiva.push (v[i]);
    }
    res.resize (stiva.size () + 1);
    g << stiva.size () << '\n', i = 1;
    while (!stiva.empty ())
    {
        res[i] = stiva.top ();
        stiva.pop (), i += 1;
    }
    for (i = res.size () - 1; i >= 1; i -= 1)
    {
        g << fixed << setprecision (6) << res[i].x << ' ';
        g << fixed << setprecision (6) << res[i].y << '\n';
    }
    return 0;
}