Cod sursa(job #1812223)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 21 noiembrie 2016 22:00:13
Problema Oypara Scor 10
Compilator cpp Status done
Runda Lista lui wefgef Marime 2.66 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#define MAXN 100050
#define inf 0x7fffffff

using namespace std;

struct segm
{
    int x, y1, y2; /// y1 jos, y2 sus
    segm(int x = 0, int y1 = 0, int y2 = 0) : x(x), y1(y1), y2(y2) { }
    bool operator()(segm a, segm b)
    {
        return a.x < b.x;
    }
};
struct punct
{
    int x, y;
    punct(int x = 0, int y = 0) : x(x), y(y) { }
    bool operator()(punct a, punct b)
    {
        return a.x < b.x;
    }
};
struct interv
{
    double yes[MAXN];
};
int n;
segm a[MAXN];
punct ups[MAXN], dns[MAXN], sol1, sol2;
double sol2y;
interv sus, jos;

void read()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d %d %d", &a[i].x, &a[i].y1, &a[i].y2);
        ups[i] = punct(a[i].x, a[i].y2);
        dns[i] = punct(a[i].x, a[i].y1);
    }
}

double det(int x1, int y1, int x2, int y2, int x3, int y3)
{
    return x1*y2 + x2*y3 + x3*y1 - x3*y2 - x2*y1 - x1*y3;
}

bool trig(int x1, int y1, int x2, int y2, int x3, int y3)
{
    return det(x1, y1, x2, y2, x3, y3) > 0;
}

bool trig(punct e, punct f, punct g)
{
    return trig(e.x, e.y, f.x, f.y, g.x, g.y);
}

vector<punct> capac;
vector<punct> coaja;

void add(vector<punct> &c, punct p)
{
    while (c.size() >= 2 && trig(c[c.size()-2], c.back(), p))
        c.pop_back();
    c.push_back(p);
}


double getY(punct e, punct f) /// the Y where d(e, f) intersects OY
{
    return ((f.x*e.y) - (e.x*f.y)) / (f.x - e.x);
}

void prepare()
{
    sort(dns+1, dns+n+1, punct());
    for (int i = 1; i <= n; i++)
        add(capac, dns[i]);
    sus.yes[0] = -inf;
    for (int i = 0; i < capac.size()-1; i++)
    {
        double y = getY(capac[i], capac[i+1]);
        sus.yes[i+1] = y;
    }
    sus.yes[capac.size()] = inf;
    sort(ups+1, ups+n+1, punct());
    for (int i = n; i >= 1; i--)
        add(coaja, ups[i]);
    jos.yes[0] = -inf;
    for (int i = 0; i < coaja.size()-1; i++)
    {
        double y = getY(coaja[i], coaja[i+1]);
        jos.yes[i+1] = y;
    }
    jos.yes[coaja.size()] = inf;

}

void solve()
{
    double goY = jos.yes[0];
    int n = coaja.size(), m = capac.size(), i, j;
    for (i = 0, j = 0; i < n-1 && j < m; i++)
    {
        while (j < m && trig(coaja[i], coaja[i+1], capac[j]))
            j++;
    }
    i = i-1;
    for (j = 0; !trig(capac[j], capac[j+1], coaja[i]); j++);
    printf("%d %d %d %d", capac[j].x, capac[j].y, coaja[i].x, coaja[i].y);
}

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

    read();
    prepare();
    solve();

    return 0;
}