Cod sursa(job #3226148)

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

using namespace std;

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 <punct> stiva(n + 1);
    int vf = 0;
    for (int i = 0; i < n; i++)
    {
        while (vf > 1 && aria(stiva[vf-1], stiva[vf], v[i]) < 0)
        {
            vf--;
        }
        stiva[++vf] = v[i];
    }
    for (int i = n - 2; i > 0; i--)
    {
        while (vf > 1 && aria(stiva[vf-1], stiva[vf], v[i]) < 0)
        {
            vf--;
        }
        stiva[++vf] = v[i];
    }
    out << vf << "\n";
    for (int i = 1; i <= vf; i++)
    {
        out << stiva[i].x << " " << stiva[i].y << "\n";
    }
    in.close();
    out.close();
    return 0;
}