Cod sursa(job #3226150)

Utilizator rapidu36Victor Manz rapidu36 Data 20 aprilie 2024 11:41:27
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.53 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

const double EPS = 1e-12;

struct punct
{
    double x, y;
};

bool cmp(punct p1, punct p2)
{
    if (p1.x == p2.x)
    {
        return (p1.y < p2.y);
    }
    return (p1.x < p2.x);
}

double aria(punct a, punct b, punct c)
{
    return (a.x - b.x) * (a.y + b.y) + (b.x - c.x) * (b.y + c.y) + (c.x - a.x) * (c.y + a.y);
}

int main()
{
    ifstream in("infasuratoare.in");
    ofstream out("infasuratoare.out");
    int n;
    in >> n;
    vector <punct> v(n);
    for (int i = 0; i < n; i++)
    {
        in >> v[i].x >> v[i].y;
    }
    sort(v.begin(), v.end(), cmp);
    vector <int> stiva(n + 1);
    vector <bool> marcat(n, false);
    int vf = 0;
    for (int i = 0; i < n; i++)
    {
        while (vf > 1 && aria(v[stiva[vf-1]], v[stiva[vf]], v[i]) < EPS)
        {
            marcat[stiva[vf]] = false;
            vf--;
        }
        stiva[++vf] = i;
        marcat[stiva[vf]] = true;
    }
    for (int i = n - 1; i >= 0; i--)
    {
        if (marcat[i])
        {
            continue;
        }
        while (vf > 1 && aria(v[stiva[vf-1]], v[stiva[vf]], v[i]) < EPS)
        {
            marcat[stiva[vf]] = false;
            vf--;
        }
        stiva[++vf] = i;
        marcat[stiva[vf]] = true;
    }
    out << vf << "\n";
    for (int i = 1; i <= vf; i++)
    {
        out << v[stiva[i]].x << " " << v[stiva[i]].y << "\n";
    }
    in.close();
    out.close();
    return 0;
}