Cod sursa(job #2974464)

Utilizator IvanAndreiIvan Andrei IvanAndrei Data 4 februarie 2023 09:41:39
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.55 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

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

const int max_size = 12e4 + 1;

struct str{
    double x, y;
};

str v[max_size], ans[max_size];
vector <str> sus, jos;

bool cmp (str x, str y)
{
    if (x.x != y.x)
    {
        return x.x < y.x;
    }
    return x.y < y.y;
}

double arie (str x, str y, str z)
{
    return x.x * y.y + x.y * z.x + y.x * z.y - y.y * z.x - x.y * y.x - x.x * z.y;
}

int main ()
{
    int n;
    in >> n;
    for (int i = 1; i <= n; i++)
    {
        in >> v[i].x >> v[i].y;
    }
    sort(v + 1, v + n + 1, cmp);
    sus.push_back(v[1]);
    jos.push_back(v[1]);
    for (int i = 2; i <= n; i++)
    {
        while (sus.size() > 1 && arie(sus[sus.size() - 2], sus[sus.size() - 1], v[i]) >= 0)
        {
            sus.pop_back();
        }
        while (jos.size() > 1 && arie(jos[jos.size() - 2], jos[jos.size() - 1], v[i]) <= 0)
        {
            jos.pop_back();
        }
        sus.push_back(v[i]);
        jos.push_back(v[i]);
    }
    sus.pop_back();
    reverse(sus.begin(), sus.end());
    sus.pop_back();
    int k = 0;
    for (auto f : jos)
    {
        ans[++k] = f;
    }
    for (auto f : sus)
    {
        ans[++k] = f;
    }
    out << k << '\n';
    for (int i = 1; i <= k; i++)
    {
        out << fixed << setprecision(12) << ans[i].x << " " << ans[i].y << '\n';
    }
    in.close();
    out.close();
    return 0;
}