Cod sursa(job #2836655)

Utilizator MateiAruxandeiMateiStefan MateiAruxandei Data 20 ianuarie 2022 18:15:27
Problema Oypara Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.75 kb

#include <bits/stdc++.h>

using namespace std;

ifstream fin("oypara.in");
ofstream fout("oypara.out");

const int NMAX(100005);
using ll = long long;
struct chestie
{
    ll x, y;
} sus[NMAX], jos[NMAX], pJ[NMAX], pS[NMAX], care;
int n, cnt[3];

ll det(chestie a, chestie b, chestie c)
{
    return ((a.x * b.y + a.y * c.x + b.x * c.y) - (b.y * c.x + a.y * b.x + a.x * c.y));
}

inline bool cmp1(chestie a, chestie b)
{
    if(a.y == b.y)
        return a.x < b.x;
    return a.y < b.y;
}

inline bool cmp2(chestie a, chestie b)
{
    return (det(care, a, b) > 0);
}

inline void solve(chestie vec[], chestie st[], int ind)
{
    sort(vec + 1, vec + n + 1, cmp1);
    if(ind == 0)
        reverse(vec + 1, vec + n + 1);
    care = vec[1];
    sort(vec + 2, vec + n + 1, cmp2);

    st[++cnt[ind]] = vec[1];
    st[++cnt[ind]] = vec[2];
    for(int i = 3; i <= n; ++i)
    {
        while(cnt[ind] >= 2 && det(st[cnt[ind] - 1], st[cnt[ind]], vec[i]) <= 0)
            --cnt[ind];
        st[++cnt[ind]] = vec[i];
    }
}

int main()
{
    fin >> n;

    for(int i = 1; i <= n; ++i)
    {
        ll x, y1, y2;
        fin >> x >> y1 >> y2;

        jos[i] = {x, y1};
        sus[i] = {x, y2};
    }

    solve(jos, pJ, 0);
    solve(sus, pS, 1);

    chestie fs;
    for(int i = 1, j = 1; i < cnt[1]; ++i)
    {
        for(; det(pS[i], pS[i + 1], pJ[j]) <= 0 && j <= cnt[0]; ++j);
        if(j == cnt[0] + 1)
        {
            fs = pS[i];
            break;
        }
    }
    for(int i = 1; i < cnt[0]; ++i)
        if(det(pJ[i], pJ[i + 1], fs) <= 0)
        {
            fout << fs.x << ' ' << fs.y << ' ' << pJ[i].x << ' ' << pJ[i].y << '\n';
            return 0;
        }
    return 0;
}