Cod sursa(job #821933)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 22 noiembrie 2012 19:57:59
Problema Oypara Scor 90
Compilator cpp Status done
Runda Lista lui wefgef Marime 2.17 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#include <bitset>

#define x first
#define y second

using namespace std;

typedef pair<double, double> Point;

const int MaxN = 100005;
const double Eps = 1e-12;

vector<Point> Up, Down;
int NSegments;
bool Solution;
Point S1, S2;

inline double Det(Point P1, Point P2, Point P3) {
    return P1.x*P2.y + P2.x*P3.y + P3.x*P1.y - P1.y*P2.x - P2.y*P3.x - P3.y*P1.x;
}

vector<Point> ConvexHull(vector<Point> Points) {
    int N = Points.size(), K = 0;
    vector<int> Stack(N+2); bitset<MaxN> Used;
    sort(Points.begin(), Points.end());
    Stack[++K] = 0;
    for (int i = 1, p = 1; i >= 0; i += (p = (i == N-1 ? -p : p))) {
        if (Used[i])
            continue;
        while (K > 1 && Det(Points[Stack[K-1]], Points[Stack[K]], Points[i]) <= -Eps)
            Used[Stack[K--]] = false;
        Used[Stack[++K] = i] = true;
    }
    vector<Point> Hull(K);
    for (int i = 0; i < K; ++i)
        Hull[i] = Points[Stack[i+1]];
    return Hull;
}

void FindLine(vector<Point> P1, vector<Point> P2, bool Side, int Sign) {
    int N = P1.size()-1, M = P2.size()-1;
    for (int i = 0, j = 0; i < N; ++i) {
        if (P1[i] < P1[i+1] != Side)
            continue;
        int Steps = 0;
        while (Steps <= M && Det(P1[i], P1[i+1], P2[j])*Sign > -Eps)
            j = (j+1)%M, ++Steps;
        if (Steps >= M) {
            Solution = true, S1 = P1[i], S2 = P1[i+1];
            return;
        }
    }
}

void Solve() {
    vector<Point> UpHull = ConvexHull(Up);
    vector<Point> DownHull = ConvexHull(Down);
    FindLine(DownHull, UpHull, false, -1);
    FindLine(UpHull, DownHull, true, 1);
}

void Read() {
    freopen("oypara.in", "r", stdin);
    scanf("%d", &NSegments);
    for (int i = 0; i < NSegments; ++i) {
        int x, y1, y2; scanf("%d %d %d", &x, &y1, &y2);
        Up.push_back(Point(x, max(y1, y2)));
        Down.push_back(Point(x, min(y1, y2)));
    }
}

void Print() {
    freopen("oypara.out", "w", stdout);
    printf("%.0lf %.0lf %.0lf %.0lf\n", S1.x, S1.y, S2.x, S2.y);
}

int main() {
    Read();
    Solve();
    Print();
    return 0;
}