Cod sursa(job #587398)

Utilizator GavrilaVladGavrila Vlad GavrilaVlad Data 4 mai 2011 19:42:25
Problema Oypara Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 2.14 kb
#include <stdio.h>
#include <algorithm>
#include <set>

using namespace std;

#define maxn 100010

int n, i, j, k, ns, x, y1, y2, nj, pt;
pair<int, pair<int, int> > s[maxn];
pair<int, int> sus[maxn], jos[maxn];

int det(int ax, int ay, int bx, int by, int cx, int cy)
{
    long long aria=1LL*ax*by+1LL*bx*cy+1LL*cx*ay-1LL*ay*bx-1LL*by*cx-1LL*cy*ax;

    if(aria>0)
        return 1;
    if(aria==0)
        return 0;
    return -1;
}

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

    scanf("%d", &n);
    for(int i=1; i<=n; ++i)
    {
        scanf("%d%d%d", &x, &y1, &y2);
        s[i]=make_pair(x, make_pair(y1, y2));
    }

    sort(s+1, s+n+1);

    for(int i=1; i<=n; ++i)
    {
        jos[++nj]=make_pair(s[i].first, s[i].second.first);
        sus[++ns]=make_pair(s[i].first, s[i].second.second);

        while(ns>2 && det(sus[ns-2].first, sus[ns-2].second, sus[ns-1].first, sus[ns-1].second, sus[ns].first, sus[ns].second)<=0)
        {
            --ns;
            sus[ns]=sus[ns+1];
        }

        while(nj>2 && det(jos[nj-2].first, jos[nj-2].second, jos[nj-1].first, jos[nj-1].second, jos[nj].first, jos[nj].second)>=0)
        {
            --nj;
            jos[nj]=jos[nj+1];
        }
    }

    pt=1;
    for(int i=1; i<ns; ++i)
    {
        while(det(sus[i].first, sus[i].second, sus[i+1].first, sus[i+1].second, jos[pt].first, jos[pt].second)<=0 && pt<=nj)
            ++pt;

        if(pt==nj+1 && det(sus[i].first, sus[i].second, sus[i+1].first, sus[i+1].second, jos[1].first, jos[1].second)<=0)
        {
            printf("%d %d %d %d\n", sus[i].first, sus[i].second, sus[i+1].first, sus[i+1].second);
            return 0;
        }
    }

    pt=1;
    for(int i=1; i<nj; ++i)
    {
        while(det(jos[i].first, jos[i].second, jos[i+1].first, jos[i+1].second, sus[pt].first, sus[pt].second)>=0 && pt<=ns)
            ++pt;

        if(pt==ns+1 && det(jos[i].first, jos[i].second, jos[i+1].first, jos[i+1].second, sus[1].first, sus[1].second)>=0)
        {
            printf("%d %d %d %d\n", jos[i].first, jos[i].second, jos[i+1].first, jos[i+1].second);
            return 0;
        }
    }


    return 0;
}