Cod sursa(job #3281057)

Utilizator unomMirel Costel unom Data 28 februarie 2025 11:24:38
Problema Rubarba Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <fstream>
#include <algorithm>

using namespace std;

#define int long long

ifstream in("rubarba.in");
ofstream out("rubarba.out");
int n;
pair<int, int> v[100005];
pair<int, int> s[100005];

int det(pair<int, int> a, pair<int, int> b, pair<int, int> c)
{
    return (b.first - a.first) * (c.second - a.second) - (c.first - a.first) * (b.second - a.second);
}

int dist(pair<int, int> a, pair<int, int> b)
{
    return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}

bool cmp(const pair<int, int> &a, const pair<int, int> &b)
{
    int d = det(v[1], a, b);
    if(d == 0)
    {
        return dist(v[1], a) < dist(v[1], b);
    }

    return d < 0;
}

signed main()
{
    in>>n;

    int poz = 1;
    for(int i = 1; i<=n; i++)
    {
        in>>v[i].first>>v[i].second;

        if(v[i] < v[poz])
        {
            poz = i;
        }
    }

    swap(v[1], v[poz]);
    sort(v + 2, v + n + 1, cmp);

    s[1] = v[1];
    s[2] = v[2];
    int head = 2;

    for(int i = 3; i<=n; i++)
    {
        while(head >= 2 && det(s[head - 1], s[head], v[i]) > 0)
        {
            head--;
        }

        head++;
        s[head] = v[i];
    }

    /*for(int i = 1; i<=head; i++)
    {
        out<<s[i].first<<" "<<s[i].second<<'\n';
    }*/

    if(head >= 1)
    {
        return 1;
    }

    return 0;
}