Cod sursa(job #1149056)

Utilizator poptibiPop Tiberiu poptibi Data 21 martie 2014 13:51:47
Problema Oypara Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.29 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int NMAX = 100010;

pair<int, int> Up[NMAX], Down[NMAX], UpHull[NMAX], DownHull[NMAX], Stack[NMAX];
int N, DH, UH, K;
bool Used[NMAX];

long long Det(pair<int, int> A, pair<int, int> B, pair<int, int> C)
{
    return 1LL * A.first * (B.second - C.second) + 1LL * B.first * (C.second - A.second) + 1LL * C.first * (A.second - B.second);
}

void ConvexHull(pair<int, int> P[NMAX], pair<int, int> Hull[NMAX], int &Cnt)
{
    sort(P + 1, P + N + 1);
    K = 0;
    Stack[K ++] = P[1];
    Stack[K ++] = P[2];

    for(int i = 3; i <= N; ++ i)
    {
        while(K >= 2 && Det(Stack[K - 2], Stack[K - 1], P[i]) < 0) K --;
        Stack[K ++] = P[i];
    }

    for(int i = 0; i < K - 1; ++ i) Hull[++Cnt] = Stack[i];

    K = 0;
    Stack[K ++] = P[N];
    Stack[K ++] = P[N - 1];
    for(int i = N - 2; i > 0; -- i)
    {
        while(K >= 2 && Det(Stack[K - 2], Stack[K - 1], P[i]) < 0) K --;
        Stack[K ++] = P[i];
    }
    for(int i = 0; i < K - 1; ++ i) Hull[++Cnt] = Stack[i];
}

int Next(int X, int N)
{
    if(X == N) return 1;
    return X + 1;
}

void Find(pair<int, int> H1[NMAX], pair<int, int> H2[NMAX], int DH1, int DH2, int Type)
{
    for(int i = 1, j = 1; i <= DH1; ++ i)
    {
        if(Type == 0 && H1[i] < H1[i + 1]) continue;
        if(Type == 1 && !(H1[i] < H1[i + 1])) continue;

        int Cnt = 0;
        for(; Cnt <= DH2 && Det(H1[i], H1[i + 1], H2[j]) <= 0; j = Next(j, DH2), Cnt ++);

        if(Cnt >= DH2)
        {
            printf("%i %i %i %i\n", H1[i].first, H1[i].second, H1[i + 1].first, H1[i + 1].second);
            exit(0);
        }
    }
}

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

    scanf("%i", &N);
    for(int i = 1; i <= N; ++ i)
    {
        int X, Y, Z;
        scanf("%i %i %i", &X, &Y, &Z);
        Up[i] = make_pair(X, max(Y, Z));
        Down[i] = make_pair(X, min(Y, Z));
    }

    ConvexHull(Up, UpHull, UH);
    ConvexHull(Down, DownHull, DH);
    UpHull[++UH] = UpHull[1];
    DownHull[++DH] = DownHull[1];
    Find(DownHull, UpHull, DH, UH, 0);
    Find(UpHull, DownHull, UH, DH, 1);
}