Cod sursa(job #600465)

Utilizator cont_de_testeCont Teste cont_de_teste Data 1 iulie 2011 21:34:25
Problema Oypara Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.67 kb
# include <algorithm>
# include <bitset>
# include <cstdio>
# include <cstring>
# 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], B[MAX];
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 void rad (int N, int byte, pair <int, PR> *A, pair <int, PR> *B) {
    int cnt[512], C[512] = { 1 } ;
    memset ( cnt, 0, sizeof cnt ) ;
    for ( int i = 1; i <= N; ++i )
        ++cnt[ A[i].x >> byte & 511 ] ;
    for ( int i = 1; i < 512; ++i )
        C[i] = C[i - 1] + cnt[i - 1] ;
    for ( int i = 1; i <= N; ++i )
        B[ C[ A[i].x >> byte & 511 ]++ ] = A[i] ;
}

inline void radix (pair <int, PR> *A, int N) {
    rad (N, 0, A, B) ;
    rad (N, 9, B, A) ;
    rad (N, 18, A, B) ;
    rad (N, 27, B, A) ;
}

int main (void) {
    freopen (FIN, "r", stdin);

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

    vector <PR> sus, jos;
    for (int i = 1; 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);
    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]) >= 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]) >= 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]) <= 0 && check (jos[aux2], jos[i], sus[wh]) <= 0) {
            fprintf (fopen (FOU, "w"), "%d %d %d %d", jos[i].x, jos[i].y, sus[wh].x, sus[wh].y);
            return 0;
        }
    }
    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]) <= 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]) <= 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]) >= 0 && check (jos[aux2], jos[i], sus[wh]) >= 0) {
            fprintf (fopen (FOU, "w"), "%d %d %d %d", jos[i].x, jos[i].y, sus[wh].x, sus[wh].y);
            return 0;
        }
    }
}