Cod sursa(job #1812152)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 21 noiembrie 2016 21:12:49
Problema Oypara Scor 0
Compilator cpp Status done
Runda Lista lui wefgef Marime 3.16 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 coresp[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;
    sus.coresp[0] = 0;
    for (int i = 0; i < capac.size()-1; i++)
    {
        double y = getY(capac[i], capac[i+1]);
        sus.yes[i+1] = y;
        sus.coresp[i+1] = i+1;
    }
    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;
    jos.coresp[0] = 0;
    for (int i = 0; i < coaja.size()-1; i++)
    {
        double y = getY(coaja[i], coaja[i+1]);
        jos.yes[i+1] = y;
        jos.coresp[i+1] = i+1;
    }
    jos.yes[coaja.size()] = inf;

}

void solve()
{
    double goY = jos.yes[0];
    for (int i = 0, j = 0; i <= n && j <= n; )
    {
        if (trig(punct(0, goY), capac[sus.coresp[i]], coaja[jos.coresp[j]]))
        {
            //cerr << "solution " << goY << " " << coaja[jos.coresp[i]].x << " " << coaja[jos.coresp[i]].y;
            sol1 = coaja[jos.coresp[j]];
            sol2.x = sol1.x - 1;
            sol2.y = (sol2.x*sol1.y + goY) / sol1.x;
            //cerr << goY << "\n";
            //cerr << sol1.x << " " << sol1.y << " " << sol2.x << " " << sol2y;
            break;
        }
        if (sus.yes[i+1] < jos.yes[j+1])
            goY = sus.yes[++i];
        else
            goY = jos.yes[++j];
    }
}

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

    read();
    prepare();
    solve();
    printf("%d %d %d %d", sol1.x, sol1.y, sol2.x, sol2.y);

    return 0;
}