Cod sursa(job #600468)

Utilizator SpiderManSimoiu Robert SpiderMan Data 1 iulie 2011 21:40:26
Problema Oypara Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 2.46 kb
# include <algorithm>
# include <cstdio>
# include <bitset>
# include <vector>
using namespace std;

# define x first
# define y1 second.first
# define y2 second.second
# define y second

typedef pair <int, int> PR;
const char *FIN = "oypara.in", *FOU = "oypara.out";
const int MAX = 100005;

inline long long check (PR P3, PR P1, PR P2) {
    return 1LL * P3.x * (P1.y - P2.y) + 1LL * P3.y * (P2.x - P1.x) - 1LL * P1.x * (P1.y - P2.y) - 1LL * P1.y * (P2.x - P1.x);
}

pair <int, PR> seg[MAX];
vector <PR> sus, jos;
int N;

inline int in (PR A, PR B, PR C) {
    return 1LL * (A.y - B.y) * C.x + 1LL * (B.x - A.x) * C.y + (1LL * A.x * B.y) - (1LL * B.x * A.y) < 0;
}

vector <PR> convex_hull (vector <PR> &V) {
    vector <int> stk;
    vector <PR> P;
    bitset <MAX> viz;
    stk.push_back (0), stk.push_back (1), viz[1] = 1;
    for (int i = 2, wh = 1; viz[0] == 0; stk.push_back (i), viz[i] = 1) {
        for (; viz[i] ; i += wh = (i == N - 1 ? -1 : wh)) ;
        for (; stk.size () > 1 && in (V[*(stk.end () - 2)], V[stk.back ()], V[i]); viz[stk.back ()] = 0, stk.pop_back ());
    }
    for (size_t i = 0, j = stk.size () - 1; i < j; ++i)
        P.push_back (V[stk[i]]);
    stk.clear ();
    return P;
}

inline int doit (int semn) {
    for (size_t i = 0, j = jos.size (), wh = 0; i < j; ++i) {
        for (int aux = 0; true; wh = aux) {
            aux = wh == sus.size () - 1 ? 0 : wh + 1;
            if (check (sus[aux], jos[i], sus[wh]) * semn >= 0) break;
        }
        for (int aux = 0; true; wh = aux) {
            aux = wh == 0 ? sus.size () - 1 : wh - 1;
            if (check (sus[aux], jos[i], sus[wh]) * semn >= 0) break;
        }
        int aux1 = i == jos.size () - 1 ? 0 : i + 1;
        int aux2 = i == 0 ? jos.size () - 1 : i - 1;
        if (check (jos[aux1], jos[i], sus[wh]) * semn <= 0 && check (jos[aux2], jos[i], sus[wh]) * semn <= 0) {
            fprintf (fopen (FOU, "w"), "%d %d %d %d", jos[i].x, jos[i].y, sus[wh].x, sus[wh].y);
            return 0;
        }
    }
}
int main (void) {
    freopen (FIN, "r", stdin);

    scanf ("%d", &N);
    for (int i = 0; i < N; ++i)
        scanf ("%d %d %d", &seg[i].x, &seg[i].y1, &seg[i].y2);
    sort (seg, seg + N);

    for (int i = 0; i < N; ++i) {
        jos.push_back (make_pair (seg[i].x, seg[i].y1));
        sus.push_back (make_pair (seg[i].x, seg[i].y2));
    }
    jos = convex_hull (jos), sus = convex_hull (sus);
    if (doit (1)) doit (-1);
}