Cod sursa(job #3215454)

Utilizator ana_valeriaAna Valeria Duguleanu ana_valeria Data 14 martie 2024 23:25:14
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <vector>
#define MAX 120000
using namespace std;
ifstream cin ("infasuratoare.in");
ofstream cout ("infasuratoare.out");
struct ura
{
    double x, y;
};
ura v[MAX + 10];
vector <ura> up, down;
bool cmp(const ura &a, const ura &b)
{
    if (a.x < b.x)
        return true;
    if (a.x > b.x)
        return false;
    if (a.y < b.y)
        return true;
    return false;
}
double area(ura a, ura b, ura c)
{
    return (a.x * b.y + b.x * c.y + c.x * a.y - c.x * b.y - a.x * c.y - b.x * a.y);
}
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> v[i].x >> v[i].y;
    sort(v + 1, v + n + 1, cmp);
    up.push_back(v[1]);
    down.push_back(v[1]);
    for (int i = 2; i <= n; i++)
    {
        while (up.size() >= 2 && area(up[up.size() - 2], up[up.size() - 1], v[i]) >= 0)
            up.pop_back();
        up.push_back(v[i]);
        while (down.size() >= 2 && area(down[down.size() - 2], down[down.size() - 1], v[i]) <= 0)
            down.pop_back();
        down.push_back(v[i]);
    }
    up.pop_back();
    reverse(up.begin(), up.end());
    up.pop_back();
    cout << up.size() + down.size() << '\n';
    cout << fixed << setprecision(12);
    for (const auto &it : down)
        cout << it.x << ' ' << it.y << '\n';
    for (const auto &it : up)
        cout << it.x << ' ' << it.y << '\n';
    return 0;
}