Cod sursa(job #589978)

Utilizator Addy.Adrian Draghici Addy. Data 14 mai 2011 20:36:33
Problema Oypara Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.87 kb
#include <cstdio>
#include <algorithm>

using namespace std;

#define NMAX 100050
#define INF 0x3f3f3f3f
#define ll long long

struct punct {
    int x, y;
} PS[NMAX], PJ[NMAX], S[NMAX], J[NMAX];

int D[NMAX], NS, NJ, n;

bool cmp (punct, punct), convex (punct, punct, punct);
void infasuratoare (punct*, punct*, int&);

int main () {

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

    scanf ("%d", &n);

    int i, x, y1, y2;
    for (i = 1; i <= n; i++) {
        scanf ("%d %d %d", &x, &y1, &y2);
        if (y1 < y2) swap (y1, y2);
        PS[i].x = x, PS[i].y = y1;
        PJ[i].x = x, PJ[i].y = y2;
    }

    infasuratoare (PS, S, NS);
    infasuratoare (PJ, J, NJ);

    int pmin, xmin = INF;
    for (i = 1; i <= NJ; i++)
        if (J[i].x < xmin) pmin = i, xmin = J[i].x;

    int a, b;
    for (i = 1; i <= NS; i++) {
        a = i - 1, b = i + 1;
        if (i == 1) a = NS; if (i == NS) b = 1;
        if (convex (J[pmin], S[i], S[a]) && convex (J[pmin], S[i], S[b])) break;
    }

    int c = pmin - 1, d = pmin + 1;
    if (pmin == 1) c = NJ; if (pmin == NJ) d = 1;
    if (convex (J[pmin], J[c], S[i]) && convex (J[pmin], J[d], S[i])) {
        printf ("%d %d %d %d", J[pmin].x, J[pmin].y, S[i].x, S[i].y);
        return 0;
    }

    int j;
    for (j = (pmin < NJ ? pmin + 1 : 1); j != pmin; ) {
        while (!convex (J[j], S[i], S[a]) || !convex (J[j], S[i], S[b])) {
            i++; if (i == NS) i = 1; //if (i == 1) printf ("TLE!!!\n");
            a = i - 1, b = i + 1;
            if (i == 1) a = NS; if (i == NS) b = 1;
        }

        c = j - 1, d = j + 1;
        if (j == 1) c = NJ; if (j == NJ) d = 1;
        if (convex (J[j], J[c], S[i]) && convex (J[j], J[d], S[i])) {
            printf ("%d %d %d %d", J[j].x, J[j].y, S[i].x, S[i].y);
            return 0;
        }

        if (j < NJ) j++;
        else j = 1;
    }

    return 0;
}

void infasuratoare (punct *P, punct *V, int &NV) {

    int i, pmin, xmin = INF, ymin = INF;
    for (i = 1; i <= n; i++)
        if (P[i].y < ymin) pmin = i, xmin = P[i].x, ymin = P[i].y;
        else if (P[i].y == ymin && P[i].x < xmin) pmin = i, xmin = P[i].x, ymin = P[i].y;

    for (i = 1; i <= n; i++)
        P[i].x -= xmin, P[i].y -= ymin;

    swap (P[1], P[pmin]);
    sort (P + 2, P + 1 + n, cmp);

    int N = 2; D[1] = 1, D[2] = 2;
    for (i = 3; i <= n; i++) {
        while (N > 2 && !convex (P[ D[N-1] ], P[ D[N] ], P[i])) N--;
        D[++N] = i;
    }

    NV = N;
    for (i = 1; i <= N; i++)
        V[i].x = P[ D[i] ].x + xmin, V[i].y = P[ D[i] ].y + ymin;
}

bool cmp (punct a, punct b) {

    return (ll) a.x * b.y > (ll) b.x * a.y;
}

bool convex (punct a, punct b, punct c) {

    ll S = (ll) (a.x - c.x) * (ll) (b.y - c.y) - (ll) (b.x - c.x) * (ll) (a.y - c.y);
    return S >= 0;
}