Cod sursa(job #3293053)

Utilizator CaldareaCiprianCaldarea Ciprian CaldareaCiprian Data 10 aprilie 2025 10:50:20
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <stack>
#include <vector>
#include <typeinfo>
#include <iomanip>

using namespace std;

#define yp first
#define xp second

using ld = long double;
using PD = pair<long double, long double>;
using VPD = vector<PD>;

VPD v;

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

long double CrossProduct(PD A, PD B, PD C)
{
    return (B.xp - A.xp) * (C.yp - A.yp) - (B.yp - A.yp) * (C.xp - A.xp);
}

int main()
{
    int n;
    fin >> n;
    v.reserve(n);
    ld x, y;
    int pos = 0;
    PD cur = make_pair(.1L * 1000000001, .1L * 1000000001);
    for (int i = 1; i <= n; ++i)
    {
        fin >> x >> y;
        v.emplace_back(y, x);

        if (cur > v[i - 1])
        {
            cur = v[i - 1];
            pos = i - 1;
        }

    }

    swap(v[0], v[pos]);

    sort(v.begin() + 1, v.end(), [](PD B, PD C)
         {
            return CrossProduct(v[0], B, C) > 0;
         });


    vector<int> vstk(n + 1);
    vstk[0] = 0;
    vstk[1] = 1;
    int top = 1;

    for (int i = 2; i < n; ++i)
    {
        while (top >= 1 && CrossProduct(v[vstk[top - 1]], v[vstk[top]], v[i]) < 0)
            --top;

        vstk[++top] = i;
    }

    fout << top + 1 << '\n';

    for (int i = 0; i <= top; ++i)
    {
        fout << fixed << setprecision(12) << v[vstk[i]].xp << ' ' << v[vstk[i]].yp << '\n';
    }


}