Cod sursa(job #3291516)

Utilizator mirceamaierean41Mircea Maierean mirceamaierean41 Data 4 aprilie 2025 22:54:02
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <fstream>
#include <math.h>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

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

const double oo = 0x3f3f3f3f;
const double eps = 1e-12;

struct point
{
    double x, y;
};

vector<point> v;
int n;

inline double determ(const point &a, const point &b, const point &c)
{
    return a.x * b.y + b.x * c.y + c.x * a.y - a.y * b.x - b.y * c.x - c.y * a.x;
}

inline bool cmp(const point &a, const point &b)
{
    return determ(v[0], a, b) < 0;
}

int main()
{
    point a, left;
    int index = 0;
    left = {oo, oo};
    fin >> n;
    for (int i = 0; i < n; ++i)
    {
        fin >> a.x >> a.y;
        v.push_back(a);
        if (a.x < left.x || (abs(a.x - left.x) < eps && a.y < left.y))
        {
            left = a;
            index = i;
        }
    }

    swap(v[0], v[index]);
    sort(v.begin() + 1, v.end(), cmp);

    vector<point> st;
    st.push_back(v[0]);
    st.push_back(v[1]);

    for (int i = 2; i < n; ++i)
    {
        while (st.size() > 1 && determ(st[st.size() - 2], st[st.size() - 1], v[i]) > 0)
            st.pop_back();
        st.push_back(v[i]);
    }

    fout << st.size() << '\n';
    fout << fixed << setprecision(12);

    for (int i = st.size() - 1; i >= 0; --i)
        fout << st[i].x << " " << st[i].y << '\n';

    return 0;
}