Cod sursa(job #3224728)

Utilizator andrei_marciucMarciuc Andrei andrei_marciuc Data 15 aprilie 2024 22:22:53
Problema Oypara Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

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

#define x first
#define y second
typedef pair<long long,long long> point;

vector<point> sus, jos;
vector<point> ls, lj;
int n;

long long id(point a,point b, point c) {
    long long sum = b.x * c.y + c.x * a.y + a.x * b.y;
    long long dif = a.x * c.y + c.x * b.y + b.x * a.y;
    return sum - dif <= 0LL;
}

vector<point> ic(vector<point> p, int s) {
    sort(p.begin(), p.end());
    if(s)
        reverse(p.begin(), p.end());
    
    vector<point> st;
    st.push_back(p[0]);
    st.push_back(p[1]);
    for(int i = 2; i < p.size(); i++) {
        for(; st.size() > 1 && id(st[st.size() - 2], st[st.size() - 1], p[i]); st.pop_back());
        st.push_back(p[i]);
    }
    return st;
}

point p1;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    in >> n;

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

        in >> x >> y1 >> y2;

        jos.push_back(make_pair(x, y1));
        sus.push_back(make_pair(x, y2));
    }

    lj = ic(jos, 1);
    ls = ic(sus, 0);

    for(int i = 0, j = 0; i + 1 < ls.size(); i++) {
        for(; id(ls[i], ls[i + 1], lj[j]) && j < lj.size(); ++j);

        if(j == lj.size()) {
            p1 = ls[i];
            break;
        }
    }

    for(int i = 0; i + 1 < lj.size(); i++)
        if(id(lj[i], lj[i + 1], p1)) {
            out << p1.x << ' ' << p1.y << ' ' << lj[i].x << ' ' << lj[i].y << '\n';
            return 0;
        }

    return 0;
}