Cod sursa(job #3364887)

Utilizator JenJenCristache Ion JenJen Data 12 septembrie 2026 22:08:02
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>

using namespace std;

#define MAX 120005

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

struct Punct
{
    double x, y;
};

int n;
double x, y;
vector <Punct> v;
int minn;
vector <Punct> rez;

double arie(const Punct& a, const Punct& b, const Punct& c)
{
    return 0.5*(a.x*(b.y - c.y) + b.x*(c.y - a.y) + c.x*(a.y - b.y));
}

bool cmp(const Punct& a, const Punct& b)
{
    return arie(v[0], a, b) >= 0;
}

Punct a, b, c;

int main()
{
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        cin >> x >> y;
        v.push_back({x, y});
        if (v[i].y < v[minn].y) minn = i;
    }

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

    rez.push_back(v[0]);
    rez.push_back(v[1]);

    for (int i = 2; i < n; i++)
    {
        while (arie(rez[rez.size() - 2], rez[rez.size() - 1], v[i]) < 0)
            rez.pop_back();

        rez.push_back(v[i]);
    }

    cout << rez.size() << '\n';
    for (int i = 0 ; i < rez.size(); i++)
    {
        cout << fixed << setprecision(6) << rez[i].x << " ";
        cout << fixed << setprecision(6) << rez[i].y << "\n";

    }
    return 0;
}