Cod sursa(job #1202285)

Utilizator andreiiiiPopa Andrei andreiiii Data 27 iunie 2014 16:04:28
Problema Oypara Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.58 kb
#include <algorithm>
#include <bitset>
#include <cstdio>
#include <vector>

using namespace std;

class Point {
public:
    int x, y;

    Point() {}
    Point (const int _x, const int _y):
        x(_x),
        y(_y) {}

    bool operator<(const Point &e) const
    {
        if (x != e.x) return x < e.x;
        return y < e.y;
    }
};

long long Det(const Point &o, const Point &a, const Point &b)
{
    return 1LL * (a.x - o.x) * (b.y - o.y) - 1LL * (b.x - o.x) * (a.y - o.y);
}

bitset <100005> Used;
vector<Point> ConvexHull(const vector<Point> &Points)
{
    vector<int> UsedPoints;
    Used.reset();

    for (int i = 0; i < int(Points.size()); i++)
    {
        while (UsedPoints.size() > 1U && Det(Points[UsedPoints[UsedPoints.size() - 2]], Points[UsedPoints[UsedPoints.size() - 1]], Points[i]) < 0)
        {
            Used[UsedPoints.back()] = 0;
            UsedPoints.pop_back();
        }
        UsedPoints.push_back(i);
        Used[i] = 1;
    }

    Used[0] = 0;
    for (int i = Points.size() - 2; i >= 0; i--)
    {
        if (Used[i]) continue;
        while (UsedPoints.size() > 1U && Det(Points[UsedPoints[UsedPoints.size() - 2]], Points[UsedPoints[UsedPoints.size() - 1]], Points[i]) < 0)
        {
            Used[UsedPoints.back()] = 0;
            UsedPoints.pop_back();
        }
        UsedPoints.push_back(i);
        Used[i] = 1;
    }

    vector<Point> Hull(UsedPoints.size() - 1);
    for (int i = 0; i < int(Hull.size()); i++)
        Hull[i] = Points[UsedPoints[i]];

    return Hull;
}

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

    int N;
    scanf("%d", &N);

    vector<Point> Polygon1(N), Polygon2(N);

    for (int i = 0; i < N; i++)
    {
        int x, y1, y2;
        scanf("%d%d%d", &x, &y1, &y2);

        Polygon1[i] = Point(x, y2);
        Polygon2[i] = Point(x, y1);
    }

    sort(Polygon1.begin(), Polygon1.end());
    sort(Polygon2.begin(), Polygon2.end());

    Polygon1 = ConvexHull(Polygon1);
    Polygon2 = ConvexHull(Polygon2);

    for (int i = 0, j = 0; i < int(Polygon1.size()); i++)
    {
        for (int next = (j + 1) % Polygon2.size(); Det(Polygon2[next], Polygon1[i], Polygon2[j]) < 0;)
        {
            j = next;
            next = (j + 1) % Polygon2.size();
        }
        for (int prev = j ? j - 1: Polygon2.size() - 1; Det(Polygon2[prev], Polygon1[i], Polygon2[j]) < 0;)
        {
            j = prev;
            prev = j ? j - 1: Polygon2.size() - 1;
        }

        int next = (i + 1) % Polygon1.size(), prev = i ? i - 1: Polygon2.size() - 1;

        if (Det(Polygon1[prev], Polygon1[i], Polygon2[j]) <= 0 && Det(Polygon1[next], Polygon1[i], Polygon2[j]) <= 0)
        {
            printf("%d %d %d %d\n", Polygon1[i].x, Polygon1[i].y, Polygon2[j].x, Polygon2[j].y);
            return 0;
        }
    }

    for (int i = 0, j = 0; i < int(Polygon1.size()); i++)
    {
        for (int next = (j + 1) % Polygon2.size(); Det(Polygon2[next], Polygon1[i], Polygon2[j]) > 0;)
        {
            j = next;
            next = (j + 1) % Polygon2.size();
        }
        for (int prev = j ? j - 1: Polygon2.size() - 1; Det(Polygon2[prev], Polygon1[i], Polygon2[j]) > 0;)
        {
            j = prev;
            prev = j ? j - 1: Polygon2.size() - 1;
        }

        int next = (i + 1) % Polygon1.size(), prev = i ? i - 1: Polygon2.size() - 1;

        if (Det(Polygon1[prev], Polygon1[i], Polygon2[j]) >= 0 && Det(Polygon1[next], Polygon1[i], Polygon2[j]) >= 0)
        {
            printf("%d %d %d %d\n", Polygon1[i].x, Polygon1[i].y, Polygon2[j].x, Polygon2[j].y);
            return 0;
        }
    }
}