Cod sursa(job #3289758)

Utilizator Ruxandra009Ruxandra Vasilescu Ruxandra009 Data 28 martie 2025 13:40:06
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <algorithm>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

const int nmax = 120005;

struct ceva{
    double x, y;
}v[nmax];

int n;
vector<ceva> ans;

int det(ceva a, ceva b, ceva c)
{
    double d = (c.y - a.y) * (b.x - a.x) - (c.x - a.x) * (b.y - a.y);

    if(d < 0) return -1;
    if(d > 0) return 1;
    return 0;
}

bool cmp(ceva a, ceva b){
    if(a.y != b.y) return a.y < b.y;
    return a.x < b.x;
}

int main()
{
    f >> n;
    for(int i = 1; i <= n; i ++)
        f >> v[i].x >> v[i].y;

    sort(v + 1, v + n + 1, cmp);

    ans.push_back(v[1]); ans.push_back(v[2]);
    for(int i = 3; i <= n; i ++)
    {
        while(ans.size() > 1 && det(ans[ans.size() - 2], ans.back(), v[i]) < 0)
            ans.pop_back();

        ans.push_back(v[i]);
    }

    for(int i = n - 1; i >= 1; i --)
    {
        while(ans.size() > 1 && det(ans[ans.size() - 2], ans.back(), v[i]) < 0)
            ans.pop_back();

        ans.push_back(v[i]);
    }

    g << ans.size() - 1 << '\n';
    for(int i = 0; i < ans.size() - 1; i ++)
        g << ans[i].x << " " << ans[i].y << '\n';
    return 0;
}