Cod sursa(job #3221723)

Utilizator IvanAndreiIvan Andrei IvanAndrei Data 7 aprilie 2024 21:28:25
Problema Oypara Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.25 kb
/// la multi ani la arici <3
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define ordered_set tree <long long, null_type, less<long long>, rb_tree_tag, tree_order_statistics_node_update>
#define lsb(x)(x & (-x))

const int max_size = 2e5 + 20;

pair <int, int> jos[max_size], sus[max_size];
int n, k, t;

int arie (pair <int, int> x, pair <int, int> y, pair <int, int> z)
{
    return x.first * (y.second - z.second) + y.first * (z.second - x.second) + z.first * (x.second - y.second);
}

int lowhull ()
{
    vector <pair <int, int>> aux;
    for (int i = 1; i <= n; i++)
    {
        while (aux.size() > 1 && arie(aux[aux.size() - 2], aux.back(), sus[i]) <= 0)
        {
            aux.pop_back();
        }
        aux.push_back(sus[i]);
    }
    for (int i = 0; i < aux.size(); i++)
    {
        sus[i + 1] = aux[i];
    }
    return aux.size();
}

int uphull ()
{
    vector <pair <int, int>> aux;
    for (int i = 1; i <= n; i++)
    {
        while (aux.size() > 1 && arie(aux[aux.size() - 2], aux.back(), jos[i]) >= 0)
        {
            aux.pop_back();
        }
        aux.push_back(jos[i]);
    }
    for (int i = 0; i < aux.size(); i++)
    {
        jos[i + 1] = aux[i];
    }
    return aux.size();
}

bool check (pair <int, int> x, pair <int, int> y)
{
    for (int i = 1; i <= k; i++)
    {
        if (arie(x, y, sus[i]) < 0)
        {
            return 0;
        }
    }
    for (int i = 1; i <= t; i++)
    {
        if (arie(x, y, jos[i]) > 0)
        {
            return 0;
        }
    }
    return 1;
}

void solve ()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> jos[i].first >> jos[i].second >> sus[i].second;
        sus[i].first = jos[i].first;
    }
    sort(jos + 1, jos + n + 1);
    sort(sus + 1, sus + n + 1);
    k = lowhull(), t = uphull();
    int i = 1, j = 1;
    while (j <= t && arie(sus[1], sus[2], jos[j]) <= 0)
    {
        j++;
    }
    while (i < k && j <= t)
    {
        while (j <= t && arie(sus[i], sus[i + 1], jos[j]) <= 0)
        {
            j++;
        }
        i++;
    }
    if (i < k && check(sus[i], sus[i + 1]))
    {
        cout << sus[i].first << " " << sus[i].second << " " << sus[i + 1].first << " " << sus[i + 1].second;
        return;
    }
    i = 1, j = 1;
    while (i <= k && arie(jos[1], jos[2], sus[i]) >= 0)
    {
        i++;
    }
    while (i <= k && j < t)
    {
        while (i <= k && arie(jos[j], jos[j + 1], sus[i]) >= 0)
        {
            i++;
        }
        j++;
    }
    if (j < t && check(jos[j], jos[j + 1]))
    {
        cout << jos[j].first << " " << jos[j].second << " " << jos[j + 1].first << " " << jos[j + 1].second;
    }
    cout << '\n';
}

signed main ()
{
#ifdef LOCAL
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#else
    freopen("oypara.in", "r", stdin);
    freopen("oypara.out", "w", stdout);
#endif // LOCAL
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    long long tt;
    //cin >> tt;
    tt = 1;
    while (tt--)
    {
        solve();
    }
    return 0;
}