Cod sursa(job #1341140)

Utilizator PaueyPaula Nicoleta Gradu Pauey Data 12 februarie 2015 15:10:23
Problema A+B Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.82 kb
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <set>
using namespace std;

struct moto {
    double a, b, k, q, v, mst, mdr;
};

const int MAXN = 50005;
const double inf = 2000000000;

moto x[MAXN], x2[MAXN];
set<double> ans;
int N, L;

bool cmp(moto x, moto y) {
    return x.v < y.v;
}

void solve(int i) {
    if(x[i].b + x[N].a - x[i].a) {
        double vc = (L - x[i].q - x[N].k + x[i].k) / (x[i].b + x[N].a- x[i].a);
        cout << vc << ' ' << i << '\n';
        if(vc < x[i + 1].v && vc >= x[i].v && ((x2[i].b > 0 && vc > x[i].mst) || (x2[i].b < 0 && vc < x[i].mst)) && ((x2[i + 1]. a > 0 && vc > x[i + 1].mdr) || (x2[i + 1]. a < 0 && vc < x[i + 1].mdr)))
            ans.insert(vc);
    }
}

int main()
{
    ifstream cin("xmoto.in");
    //ofstream cout("xmoto.out");
    cin >> N >> L;
    for(int i = 1; i <= N; ++i) {
        cin >> x[i].a >> x[i].b >> x[i].k >> x[i].q >> x[i].v;
        x2[i].a = x[i].a;
        x2[i].b = x[i].b;
        x2[i].k = x[i].k;
        x2[i].q = x[i].q;
    }
    sort(x + 1, x + N + 1, cmp);
    x[0].mst = -inf;
    x[N + 1].mdr = -inf;
    x[1].mst = - x[1].q / x[1].b;
    x[N].mdr = - x[N].k / x[N].a;
    for(int i = 2; i <= N; ++i) {
        x[i].a += x[i - 1].a;
        x[i].b += x[i - 1].b;
        x[i].k += x[i - 1].k;
        x[i].q = x[i - 1].q;
        x[i].mst = max(x[i - 1].mst, - x2[i].q / x2[i].b);
    }
    for(int i = N - 1; i > 0; --i) {
        x[i].mdr = max(x[i + 1].mdr, - x2[i].k / x2[i].a);
    }
    x[0].v = 0;
    x[N + 1].v = inf;
    for(int i = 0; i <= N; ++i) {
        solve(i);
    }
    cout << ans.size() << '\n';
    for(set<double>:: iterator it = ans.begin(); it != ans.end(); ++it) {
        cout << fixed << setprecision(6) << *it << ' ';
    }
    return 0;
}