Cod sursa(job #1601197)

Utilizator RazvanR104Razvan-Andrei Ciocoiu RazvanR104 Data 15 februarie 2016 20:02:38
Problema Oypara Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.51 kb
#include <bits/stdc++.h>

using namespace std;

typedef int64_t i64;
const int NMAX = 100010;

int N;

struct Point {
    int x, y;
    Point(int x = 0, int y = 0) : x(x), y(y) {}

    bool operator <(const Point &rhs) const {
        return (x == rhs.x) ? (y < rhs.y) : (x < rhs.x);
    }

    bool operator >(const Point &rhs) const {
        return (x == rhs.x) ? (y > rhs.y) : (x > rhs.x);
    }
};
vector<Point> Up, Down;

i64 Area(Point A, Point B, Point C) {
    return i64(B.x - A.x) * (C.y - A.y) - i64(C.x - A.x) * (B.y - A.y);
}

void LowerEnvelope(vector<Point> &hull) {
    sort(hull.begin(), hull.end());

    vector<Point> curr;
    curr.push_back(hull[0]);
    curr.push_back(hull[1]);

    for (int i = 2; i < int(hull.size()); ++i) {
        while (curr.size() > 1 && Area(curr[curr.size() - 2], curr[curr.size() - 1], hull[i]) <= 0)
            curr.pop_back();
        curr.push_back(hull[i]);
    }

    curr.push_back(hull[0]);
    swap(hull, curr);
}

void UpperEnvelope(vector<Point> &hull) {
    sort(hull.begin(), hull.end(), greater<Point>());

    vector<Point> curr;
    curr.push_back(hull[0]);
    curr.push_back(hull[1]);

    for (int i = 2; i < int(hull.size()); ++i) {
        while (curr.size() > 1 && Area(curr[curr.size() - 2], curr[curr.size() - 1], hull[i]) <= 0)
            curr.pop_back();
        curr.push_back(hull[i]);
    }

    curr.push_back(hull[0]);
    swap(hull, curr);
}

int main() {
	ios_base::sync_with_stdio(false);
	#ifndef ONLINE_JUDGE
	assert(freopen("oypara.in", "r", stdin) != NULL);
    assert(freopen("oypara.out", "w", stdout) != NULL);
    assert(freopen("debug.err", "w", stderr) != NULL);
    #endif

    int i, j, x, y1, y2;

    cin >> N;
    for (i = 1; i <= N; ++i) {
        cin >> x >> y1 >> y2;
        Up.push_back(Point(x, y2));
        Down.push_back(Point(x, y1));
    }

    LowerEnvelope(Up);
    UpperEnvelope(Down);

    int solup = -1, soldown = -1;

    for (i = 0, j = 0; i + 1 < int(Up.size()); ++i) {
        while (j < int(Down.size()) && Area(Up[i], Up[i + 1], Down[j]) <= 0)
            ++j;

        if (j == Down.size()) {
            solup = i;
            break;
        }
    }

    for (i = 0; i + 1 < int(Down.size()); ++i) {
        if (Area(Down[i], Down[i + 1], Up[solup]) <= 0) {
            soldown = i;
            break;
        }
    }

    cout << Up[solup].x << ' ' << Up[solup].y << ' ' << Down[soldown].x << ' ' << Down[soldown].y << '\n';
	return 0;
}