Cod sursa(job #2836809)

Utilizator NostressmamenNu ma stresez Nostressmamen Data 20 ianuarie 2022 22:10:38
Problema Oypara Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.76 kb

#include <bits/stdc++.h>

using namespace std;

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

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

double 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 + 1; ++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)
    {
        int x, y1, y2;
        fin >> x >> y1 >> y2;

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

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

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