p540.cpp
======================
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n, s, v_min, v_max;
vector<int> xi, ri, gi, di;

void read() {
    cin >> n >> s >> v_min >> v_max;
    xi.resize(n);
    ri.resize(n);
    gi.resize(n);
    di.resize(n);
    for(int i = 0; i < n; i++) {
        cin >> xi[i] >> ri[i] >> gi[i] >> di[i];
    }
}

void solve() {
    // To have a green wave, for each traffic light we want the time we pass
    // ti = xi / v0, to be withing the green periods, or:
    //
    //        ti   \in [di - gi + k*(gi+ri)  ; di + k*(gi+ri)            ].
    //
    //     xi / v0 \in [di - gi + k*(gi+ri)  ; di + k*(gi+ri)            ].
    //
    //        v0   \in [xi / (di + k*(gi+ri)); xi / (di - gi + k*(gi+ri))].
    //
    // This means that the range of v0 will be the union or some ranges. If we
    // could compactly encode the set of v0, we could do a DP[traffic
    // light][set of v0 that are available]. The issue is that the set above
    // depends on k, and it's a floating point number. However, we can notice
    // that it's enough to notice that it's always possible for the v0 to lie on
    // a border of one of these ranges. Then it's clear which traffic lights we
    // violated and which we don't. In terms of candidates, we know that the
    // candidates have 10 <= v0 <= 50, so for any i, there are less than ~50
    // possible values for k, or overall that's around a million. This directly
    // gives us a O(#candidates * n) solution, but instead we can notice that
    // for each traffic light i, the ranges are non-overlapping. This means we
    // can instead think of this problem as having some points P, and ranges
    // L,R, and figuring out the point that is covered by the largest number of
    // ranges. This can be done by maintaining an array offline with +1 on L and
    // -1 on (R+1). We should compress the coordinates too.

    vector<pair<double, int>> events;

    for(int i = 0; i < n; i++) {
        int c = ri[i] + gi[i];
        for(int k = 0;; k++) {
            int gs = di[i] - gi[i] + k * c;
            int ge = di[i] + k * c;

            if((double)gs > (double)xi[i] / v_min) {
                break;
            }
            if(ge <= 0) {
                continue;
            }
            if((double)xi[i] / ge > (double)v_max) {
                continue;
            }

            double t_lo = max((double)gs, xi[i] / (double)v_max);
            double t_hi = min((double)ge, xi[i] / (double)v_min);
            if(t_lo < 1e-15) {
                t_lo = 1e-15;
            }
            if(t_lo > t_hi + 1e-12) {
                continue;
            }

            double vl = xi[i] / t_hi;
            double vh = xi[i] / t_lo;
            vl = max(vl, (double)v_min);
            vh = min(vh, (double)v_max);
            if(vl > vh + 1e-12) {
                continue;
            }

            events.push_back({vl, 1});
            events.push_back({vh, -1});
        }
    }

    sort(
        events.begin(), events.end(),
        [](const pair<double, int>& a, const pair<double, int>& b) {
            if(a.first != b.first) {
                return a.first < b.first;
            }
            return a.second > b.second;
        }
    );

    int cnt = 0, best_cnt = 0;
    double best_v = v_max;

    for(int i = 0; i < (int)events.size();) {
        double pos = events[i].first;
        while(i < (int)events.size() && events[i].first == pos &&
              events[i].second > 0) {
            cnt++;
            i++;
        }
        if(cnt > best_cnt || (cnt == best_cnt && pos > best_v)) {
            best_cnt = cnt;
            best_v = pos;
        }
        while(i < (int)events.size() && events[i].first == pos &&
              events[i].second < 0) {
            cnt--;
            i++;
        }
    }

    const double eps = 1e-9;
    vector<int> switched;
    for(int i = 0; i < n; i++) {
        double t = xi[i] / best_v;
        int c = ri[i] + gi[i];
        double rem = fmod(t - di[i] + gi[i], (double)c);
        if(rem < -eps) {
            rem += c;
        }
        if(rem > gi[i] + eps && rem < c - eps) {
            switched.push_back(i + 1);
        }
    }

    cout << fixed << setprecision(10) << best_v << "\n";
    cout << switched.size() << "\n";
    for(int i = 0; i < (int)switched.size(); i++) {
        if(i) {
            cout << " ";
        }
        cout << switched[i];
    }
    if(!switched.empty()) {
        cout << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}

=================
p540.in1
======================
3 1000 10 30
500 10 10 10
501 10 10 0
600 10 10 0

=================
p540.ans1
======================
16.7000000000
0

=================
p540.in2
======================
2 1000 10 30
500 10 10 10
600 10 20 2

=================
p540.in3
======================
4 1000 10 30
800 10 15 20
500 20 10 15
501 20 10 5
600 10 20 15

=================
p540.ans3
======================
20.0400000000
1
2 

=================
p540.ans2
======================
25.0000000000
0

=================
statement.txt
======================
540. Traffic Lights
Time limit per test: 1 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard

The main street of Berland's capital is a segment with length s. The main street has traffic lights installed along it. The traffic lights have been functioning since time immemorial, cyclically changing colors from red to green and vice versa. Each traffic light can be described by four numbers xi, ri, gi, di, which stand for:
xi — the distance from the beginning of the street to the traffic light (1 ≤ xi ≤ s-1),
ri — the duration of the red light illumination (10 ≤ ri ≤ 20),
gi — the duration of the green light illumination (10 ≤ gi ≤ 20),
di — the minimum non-negative moment of time when the traffic light changes the light from green to red (0 ≤ di < ri+gi).


Each traffic light retains its light cycle from the ancient past.

The King of Berland asked the transport minister to customize the traffic lights according to a "green wave" principle. That means that if you start driving from the beginning of the street at the recommended speed, you can drive through the entire street without stopping, that is, you pass each traffic light when it has the green light on.

Now it is time to show the "green wave" to the King, but the work is not even started yet. You may assume that the King starts driving at the moment of time 0 from the beginning of the street. So the minister decided to choose some speed v0 and tell the king that the "green wave" works specifically for this speed. Moreover, they can switch any number of traffic lights to the "always green" mode. The minister' aim is to ensure that if the King drives through the street at the recommended speed v0 he encounters no red traffic light. Driving exactly at the moment when the colors are changed is not considered driving through the red light.

Any transport's maximum speed is limited in Berland: it should not exceed vmax. On the other hand, the King will be angry if the recommended speed is less than vmin. Thus, the minister should choose such value of v0, which satisfies the inequation vmin ≤ v0 ≤ vmax.

Help the minister to find such v0 value, that the number of traffic lights to switch to the "always green" mode is minimum. If v0 is not uniquely defined, choose the maximum possible value of v0.

Input
The first line of the input data contains four integers n, s, vmin and vmax (1 ≤ n < 20000, 1 ≤ s ≤ 20000, 10 ≤ vmin ≤ vmax ≤ 50), where n is the number of traffic lights on the street, s is the length of the street in meters, vmin and vmax are speed limits in meters per second.

Then n lines contain descriptions of the traffic lights, one per line. Each description consists of four integer numbers xi, ri, gi, di (1 ≤ xi ≤ s-1, 10 ≤ ri,gi ≤ 20, 0 ≤ di < ri+gi), where xi, ri, gi, di are explained above. Values ri, gi, di are given in seconds and xi — in meters. No two traffic lights are located at one point.

Output
On the first line, print the sought value v0 containing no less than 10 digits after the decimal point. On the second line, print the number of traffic lights that need to be switched to the "always green" mode for the found v0. The third line should contain the numbers of those traffic lights. It doesn't matter you print empty third line or print only two lines in case of no traffic lights to switch. The traffic lights are numbered starting from 1 in the order in which they appear in the input data. Print the numbers of the traffic lights in any order.

Example(s)
sample input
sample output
3 1000 10 30
500 10 10 10
501 10 10 0
600 10 10 0
16.7000000000
0

sample input
sample output
2 1000 10 30
500 10 10 10
600 10 20 2
25.0000000000
0

sample input
sample output
4 1000 10 30
800 10 15 20
500 20 10 15
501 20 10 5
600 10 20 15
20.0400000000
1
2 

=================
