Cod sursa(job #1328022)

Utilizator geniucosOncescu Costin geniucos Data 27 ianuarie 2015 20:48:03
Problema Oypara Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 2.84 kb
#include<cstdio>
#include<algorithm>

using namespace std;

int N, nr_sus, nr_jos;

struct interval
{
    int x, st, dr;
}I[100009];

struct cmp
{
    inline bool operator () (const interval &a, const interval &b) const
    {
        return a.x < b.x;
    }
};

struct point
{
    int x, y;

    point ()
    {
        x = y = 0;
    }

    point (int x, int y)
    {
        this->x = x;
        this->y = y;
    }
}sus[100009], jos[100009], aux[100009];

void afis (point a)
{
    printf ("%d %d\n", a.x, a.y);
}

long long det (point a, point b, point c)
{
    return (long long) 1LL * a.x * b.y + 1LL * b.x * c.y + 1LL * c.x * a.y - 1LL * a.x * c.y - 1LL * b.x * a.y - 1LL * c.x * b.y;
}

void upper_envelope ()
{
    sus[1] = point (I[1].x, I[1].dr);
    sus[2] = point (I[2].x, I[2].dr);
    nr_sus = 2;
    for (int i=3; i<=N; i++)
    {
        point curr = point (I[i].x, I[i].dr);
        while (nr_sus >=2 && det (sus[nr_sus - 1], sus[nr_sus], curr) < 0)
            nr_sus --;
        sus [++nr_sus] = curr;
    }

    /*printf ("sus:\n");
    for (int i=1; i<=nr_sus; i++)
        afis (sus[i]);*/
}

void lower_envelope ()
{
    jos[1] = point (I[1].x, I[1].st);
    jos[2] = point (I[2].x, I[2].st);
    nr_jos = 2;
    for (int i=3; i<=N; i++)
    {
        point curr = point (I[i].x, I[i].st);
        while (nr_jos >=2 && det (jos[nr_jos - 1], jos[nr_jos], curr) > 0)
            nr_jos --;
        jos [++nr_jos] = curr;
    }

    /*printf ("sus:\n");
    for (int i=1; i<=nr_jos; i++)
        afis (jos[i]);*/
}

int next (int j)
{
    if (j == nr_jos)
        return 1;
    return j + 1;
}

bool intersect (point a, point b, point c, point d)
{
    long long v1 = det (a, c, b), v2 = det (a, d, b);
    if (v1 < 0 && v2 > 0) return 1;
    if (v1 > 0 && v2 < 0) return 1;
    return 0;
}

bool Try ()
{
    int j = 1;
    for (int i=1; i<nr_sus; i++)
    {
        int pas = 0;
        while (1)
        {
            pas ++;
            if (pas == N+1)
            {
                printf ("%d %d %d %d\n", sus[i].x, sus[i].y, sus[i+1].x, sus[i+1].y);
                return 1;
            }

            if (intersect (sus[i], sus[i+1], jos[j], jos[next(j)])) break;

            j = next (j);
        }
    }
    return 0;
}

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", &I[i].x, &I[i].st, &I[i].dr);
sort (I + 1, I + N + 1, cmp());

upper_envelope ();
lower_envelope ();

if (Try ())
    return 0;

for (int i=1; i<=nr_sus; i++)
    aux[i] = sus[i];

for (int i=1; i<=nr_jos; i++)
    sus[i] = jos[i];

for (int i=1; i<=nr_sus; i++)
    jos[i] = aux[i];

int aux = nr_sus;
nr_sus = nr_jos;
nr_jos = aux;

Try ();

return 0;
}