Cod sursa(job #1577846)

Utilizator smaraldaSmaranda Dinu smaralda Data 23 ianuarie 2016 22:00:53
Problema Oypara Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;

const int NMAX = 1e5 + 5;
#define mp make_pair
#define ll long long

vector < pair <int, int> > sus, jos;

ll ccw (pair <int, int> p1, pair <int, int> p2, pair <int, int> p3) {
    return (ll)((ll)p2.second - (ll)p3.second) * (ll)((ll)p1.first - (ll)p3.first) - (ll)((ll)p2.first - (ll)p3.first) * (ll)((ll)p1.second - (ll)p3.second);
}

vector < pair <int, int> > convex (vector < pair<int, int> > pts) {
    vector < pair <int, int> > sol;
    int i;

    sol.push_back(pts[0]);
    sol.push_back(pts[1]);
    for(i = 2; i < pts.size(); ++ i) {
        while(sol.size() >= 2 && ccw(sol[sol.size() - 2], sol[sol.size() - 1], pts[i]) <= 0 )
                sol.pop_back();

        sol.push_back(pts[i]);
    }

    return sol;
}

int main() {
    freopen("oypara.in", "r", stdin);
    freopen("oypara.out", "w", stdout);
    int j, iSus, iJos, nSus, nJos, x, y1, y2, n, i;

    scanf("%d", &n);
    nSus = nJos = 0;
    for(i = 1; i <= n; ++ i) {
        scanf("%d%d%d", &x, &y1, &y2);

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

    sort(sus.begin(), sus.end());
    sus = convex(sus);

    sort(jos.begin(), jos.end());
    reverse(jos.begin(), jos.end());
    jos = convex(jos);
   
    j = 0;
    for(i = 0; i < sus.size() - 1; ++ i) {
        while(j < jos.size() && ccw(sus[i], sus[i + 1], jos[j]) <= 0)
            ++ j;

        if(j == jos.size()) {
            iSus = i;
            break;
        }
    }

    for(i = 0; i < jos.size() - 1; ++ i)
        if(ccw(jos[i], jos[i + 1], sus[iSus]) <= 0) {
            iJos = i;
            break;
        }

    printf("%d %d %d %d\n", sus[iSus].first, sus[iSus].second, jos[iJos].first, jos[iJos].second);
    return 0;
}