Cod sursa(job #2051506)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 29 octombrie 2017 02:16:19
Problema Oypara Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 2.7 kb
#include <cstdio>
#include <cctype>
#include <algorithm>

FILE *fin = fopen("oypara.in", "r"), *fout = fopen("oypara.out", "w");

#define BUF_SIZE 1 << 17

int pos = BUF_SIZE;
char buf[BUF_SIZE];

inline char nextch() {
    if (pos == BUF_SIZE) fread(buf, BUF_SIZE, 1, fin), pos = 0;
    return buf[pos++];
}

inline int read() {
    char ch;
    while (!isdigit(ch = nextch()));
    int x = ch - '0';
    while (isdigit(ch = nextch())) x = 10 * x + ch - '0';
    return x;
}

#define MAXN 100000

struct myc {
    int x, y;
    inline bool operator < (const myc &u) const {
        return x < u.x;
    }
} u[MAXN + 1], v[MAXN + 1];
int k, m, st[MAXN + 1];

inline long long arie(myc a, myc b, myc c) {
    return 1LL * a.x * b.y - 1LL * a.y * b.x + 1LL * b.x * c.y - 1LL * b.y * c.x + 1LL * c.x * a.y - 1LL * c.y * a.x;
}

inline void lowerEnvelope(int n) {
    std::sort(u + 1, u + n + 1);
    int vf = 0;
    for (int i = 1; i <= n; i++) {
        while (vf > 1 && arie(u[st[vf - 1]], u[st[vf]], u[i]) <= 0)
            vf--;
        st[++vf] = i;
    }
    for (int i = 1; i <= vf; i++)
        u[i] = u[st[i]];
    k = vf;
}

inline void upperEnvelope(int n) {
    std::sort(v + 1, v + n + 1);
    int vf = 0;
    for (int i = 1; i <= n; i++) {
        while (vf > 1 && arie(v[st[vf - 1]], v[st[vf]], v[i]) >= 0)
            vf--;
        st[++vf] = i;
    }
    for (int i = 1; i <= vf; i++)
        v[i] = v[st[i]];
    m = vf;
}

inline bool bun(myc a, myc b) {
    if (a.x > b.x) std::swap(a, b);
    for (int i = 1; i <= k; i++)
        if (arie(a, b, u[i]) < 0)
            return 0;
    for (int i = 1; i <= m; i++)
        if (arie(a, b, v[i]) > 0)
            return 0;
    return 1;
}

int main() {
    int n = read();
    for (int i = 1; i <= n; i++) {
        v[i].x = u[i].x = read();
        v[i].y = read();
        u[i].y = read();
    }

    lowerEnvelope(n);
    upperEnvelope(n);

    int p = 1, q = 1;
    while (q <= m && arie(u[p], u[p + 1], v[q]) <= 0)
        q++;
    while (p + 1 < k && q <= m) {
        p++;
        while (q <= m && arie(u[p], u[p + 1], v[q]) <= 0)
            q++;
    }

    if (p < k && bun(u[p], u[p + 1])) fprintf(fout, "%d %d %d %d\n", u[p].x, u[p].y, u[p + 1].x, u[p + 1].y);
    else {
        p = 1, q = 1;
        while (p <= k && arie(v[q], v[q + 1], u[p]) >= 0)
            p++;
        while (q + 1 < m && p <= k) {
            q++;
            while (p <= k && arie(v[q], v[q + 1], u[p]) >= 0)
                p++;
        }
        if (q < m && bun(v[q], v[q + 1])) fprintf(fout, "%d %d %d %d\n", v[q].x, v[q].y, v[q + 1].x, v[q + 1].y);
        else return 1;
    }

    return 0;
}