Cod sursa(job #3289750)

Utilizator Ruxandra009Ruxandra Vasilescu Ruxandra009 Data 28 martie 2025 13:16:26
Problema Infasuratoare convexa Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.68 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, fr[nmax], st[nmax], num;
vector<ceva> ans;

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

    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 cadran(ceva a)
{
    if(a.x > 0 && a.y >= 0)
        return 1;

    if(a.x <= 0 && a.y > 0)
        return 2;

    if(a.x >= 0 && a.y < 0)
        return 4;

    return 3;
}

bool cmp2(ceva a, ceva b)
{
    int c1 = cadran(a);
    int c2 = cadran(b);

    if(c1 != c2)
        return c1 < c2;
    else
        return det({0, 0}, a, b) > 0;
}

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);

    st[1] = 1; st[2] = 2; num = 2;
    fr[2] = 1;

    int ind = 3, sm = 1;
    while(!fr[1])
    {
        while(fr[ind])
        {
            if(ind == n) sm = -1;
            ind += sm;
        }

        fr[ind] = 1;
        if(ind == 1)
            break;

        while(num >= 2 && det(v[st[num - 1]], v[st[num]], v[ind]) < 0)
            fr[st[num]] = 0, num --;

        st[++ num] = ind;
    }

    for(int i = 1; i <= num; i ++) ans.push_back(v[st[i]]);

    sort(ans.begin(), ans.end(), cmp2);

    g << ans.size() << '\n';
    for(auto a : ans)
        g << a.x << " " << a.y << '\n';
    return 0;
}