Cod sursa(job #2350673)

Utilizator akaprosAna Kapros akapros Data 21 februarie 2019 17:15:20
Problema Oypara Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.8 kb
#include <bits/stdc++.h>
#define maxN 100002
#define ll long long
using namespace std;

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

/*struct Segment
{
    int x, y1, y2;
};*/
struct Point
{
    int x, y;
    bool operator < (const Point &ot) const
    {
        if (x == ot.x)
            return y < ot.y;
        return x < ot.x;
    }
} v[2][maxN];
int st[2][maxN], head[2];
bool vis[maxN];

ll CrossProd(Point O, Point A, Point B)
{
    return (ll)(A.x - O.x) * (B.y - O.y) - (ll)(B.x - O.x) * (A.y - O.y);
}
int sgn(ll val)
{
    if (val == 0) return 0;
    if (val < 0) return -1;
    return 1;
}
bool ok(Point A, Point B, Point P1, Point P2)
{
    ll a = (ll)A.y - B.y, b = (ll)B.x - A.x, c = (ll)A.x * B.y - (ll)A.y * B.x;
    ll f1 = a * P1.x + b * P1.y + c, f2 = (a * P2.x + b * P2.y + c);
    if ((f1 > 0 && f2 < 0) || (f1 < 0 && f2 > 0)) return false;
    return true;
}
void ConvexHull(int t, int n)
{
    memset(vis, 0, sizeof(vis));
    st[t][1] = 0;
    st[t][2] = 1;
    head[t] = 2;
    vis[1] = true;

    for (int i = 0, p = 1; i >= 0; i += (p = (i == n - 1 ? -p : p)))
    {
        if (vis[i]) continue;
        while (head[t] >= 2 && CrossProd(v[t][st[t][head[t] - 1]], v[t][st[t][head[t]]], v[t][i]) < 0)
            vis[st[t][head[t] --]] = false;
        st[t][++ head[t]] = i;
        vis[i] = true;
    }
    -- head[t];
}
void PrintSol(Point A, Point B)
{
    printf("%d %d %d %d\n", A.x, A.y, B.x, B.y);
    exit(0);
}
int Prv(int t, int x)
{
    ++ x;
    if (x == head[t]) x = 0;
    return x;
}
int Nxt(int t, int x)
{
    if (t)
        -- x;
    else ++ x;
    if (x == -1) x = head[t] - 1;
    if (x == head[t]) x = 0;
    return x;
}
int findUp(int a)
{
    int j = 0;
    if (v[0][st[0][a]].x == v[1][st[1][j]].x)
        j = Nxt(1, j);
    while (CrossProd(v[0][st[0][a]], v[1][st[1][j]], v[1][st[1][Nxt(1, j)]]) < 0 && Nxt(1, j) != 0)
        j = Nxt(1, j);
    return j;
}
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++ i)
    {
        int x, y1, y2;
        scanf("%d%d%d", &x, &y1, &y2);
        v[0][i] = {x, y1};
        v[1][i] = {x, y2};
    }
    for (int t = 0; t < 2; ++ t)
        ConvexHull(t, n);

    int up = findUp(0);
    int j = up;
    for (int i = 0; i < head[0] - 1; ++ i)
    {
        int nxti = Nxt(0, i);
        if (CrossProd(v[0][st[0][i]], v[0][st[0][nxti]], v[1][st[1][j]]) >= 0)
            PrintSol(v[0][st[0][i]], v[1][st[1][j]]);

        while (CrossProd(v[0][st[0][nxti]], v[1][st[1][j]], v[1][st[1][Nxt(1, j)]]) < 0 && Nxt(1, j) != up)
        {
            j = Nxt(1, j);
            if (v[0][st[0][nxti]].x == v[1][st[1][j]].x)
                j = Nxt(1, j);
        }
    }

    return 0;
}