Cod sursa(job #1805079)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 13 noiembrie 2016 14:10:41
Problema Oypara Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <bits/stdc++.h>
using namespace std;
typedef long long i64;

const int SPQR = 100005;

struct PTX {
    int x, y;

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

int n, p0, p1;
vector<PTX> pts[2], hull[2];

inline i64 ccw(const PTX &a, const PTX &b, const PTX &c) {
    return (1LL * a.x - b.x) * (c.y - b.y) - (1LL * a.y - b.y) * (c.x - b.x); }

void make_hulls(void) {
    sort(pts[0].begin(), pts[0].end());
    sort(pts[1].rbegin(), pts[1].rend());

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

void get_calipers(void) {
    int i, j;

    for(i = 0, j = 0; i < hull[0].size() - 1 && j < hull[1].size(); ++i)
        for(; j + 1 < hull[1].size() && ccw(hull[0][i], hull[0][i + 1], hull[1][j]) <= 0; ++j);
    -- i;
    p0 = i;
    p1 = j; }

int main(void) {
    freopen("oypara.in",  "r", stdin);
    freopen("oypara.out", "w", stdout);

    scanf("%d", &n);
    pts[0].resize(n);
    pts[1].resize(n);

    for(int i = 0; i < n; ++i) {
        scanf("%d%d%d", &pts[0][i].x, &pts[0][i].y, &pts[1][i].y);
        pts[1][i].x = pts[0][i].x; }

    make_hulls();
    get_calipers();

    printf("%d %d %d %d\n", pts[0][p0].x, pts[0][p0].y , pts[1][p1].x, pts[1][p1].y);

    return 0; }