Cod sursa(job #1250786)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 28 octombrie 2014 16:38:34
Problema Oypara Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.93 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#define pb push_back
#define ll long long
#define mp make_pair
#define vpt vector <pt>
using namespace std;

struct pt {
    ll x, y;
};

bool cmp(pt a, pt b) {
    return (a.x < b.x || (a.x == b.x && a.y < b.y));
}

bool cw(pt a, pt b, pt c) {
    return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y) < 0;
}

bool ccw(pt a, pt b, pt c) {
    return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y) > 0;
}

pair <vpt, vpt> convex_hull(vpt &a) {
    vector <pt> up, down;
    if (a.size() == 1)
        return mp(down, down);
    sort(a.begin(), a.end(), &cmp);
    
    pt p1 = a[0], p2 = a.back();
    up.pb(p1); down.pb(p1);
    
    for (size_t i = 1; i < a.size(); i++) {
        if (i == a.size() - 1 || cw(p1, a[i], p2)) {
            while (up.size() >= 2 && !cw(up[up.size() -2], up[up.size() - 1], a[i]))
                up.pop_back();
            up.pb(a[i]);
        }
        if (i == a.size() - 1 || ccw(p1, a[i], p2)) {
            while (down.size() >= 2 && !ccw(down[down.size() -2], down[down.size() - 1], a[i]))
                down.pop_back();
            down.pb(a[i]);
        }
    }
    a.clear();
    
    return mp(down, up);
}

inline int inters(pt a, pt b, pt c, pt d) {
    return cw(a, b, c) != cw(a, b, d);
}

void solve(vpt &a, vpt &b) {
    int pos = -1, sgn = 1;
    
    for (size_t i = 0; i < a.size() - 1; i++) {
        while (pos + sgn < (int)b.size() && pos + sgn >= 0 &&
               pos + 2 * sgn < (int)b.size() && pos + 2 * sgn >= 0 &&
               !inters(a[i], a[i + 1], b[pos + sgn], b[pos + 2 * sgn])) {
            pos += sgn;
        }
        
        if (pos + sgn == (int)b.size() || pos + 2 * sgn == (int)b.size() || 
            pos + sgn == 0 || pos + 2 * sgn == 0) {
            sgn *= -1;
            
            while (pos + sgn < (int)b.size() && pos + sgn >= 0 &&
               pos + 2 * sgn < (int)b.size() && pos + 2 * sgn >= 0 &&
               !inters(a[i], a[i + 1], b[pos + sgn], b[pos + 2 * sgn])) {
                pos += sgn;
            }
            
            if (pos + sgn == (int)b.size() || pos + 2 * sgn == (int)b.size() || 
                pos + sgn == 0 || pos + 2 * sgn == 0) {
                printf("%lld %lld %lld %lld\n", a[i].x, a[i].y, a[i + 1].x, a[i + 1].y);
                return ;
            }
        }
    }
}

int n;
vpt A, B;

int main()
{
    freopen("oypara.in", "r", stdin);
    freopen("oypara.out", "w", stdout);
    
    scanf("%d", &n);
    int x, y, z;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d%d%d", &x, &y, &z);
        
        pt curr;
        curr.x = x; curr.y = y;
        A.pb(curr); 
        
        curr.y = z;
        B.pb(curr);
    }
    
    pair <vpt, vpt> a = convex_hull(A);
    pair <vpt, vpt> b = convex_hull(B);
    
    solve(b.first, a.second);
    return 0;
}