A binary search + line sweep

E Hashing + BIT

J prefix sum

Let's solve the problem for a tree.

The answer for a tree will be $$$n-1-l$$$ where $$$l$$$ is the length of the two farthest nodes in the tree, we can see that $$$l$$$ is the diameter of the tree.

To solve the problem, we take any tree in the graph, and solve the problem for the resulting tree, with one difference that while calculating the diameter we consider only the bridges.

const long double EPS = 1e-6;
const long double pi = 3.14159265359;

long double get(long double a, long double b, long double x, long double y) {
    return max((long double)0, min(b, y) - max(a, x));
}
int main() {
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ios_base :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T --) {
        int n, v, l, r;
        cin >> n >> v >> l >> r;
        long double x, y;
        for (int i = 1; i <= n; i++) {
            cin >> x >> y; cout << fixed << setprecision(4);
            if (x * 10 > 1.0 * v * v) {
                cout << "0.0000" << endl;
                continue;
            }
            if (l == r) {
                long double pos = 1.0 * v * v / 10 * sin(2.0 * r / 180 * pi);
                if (x - EPS <= pos && pos <= y + EPS) {
                    cout << "1.0000";
                } else {
                    cout << "0.0000";
                }
                cout << endl;
                continue;
            }
            long double lf = asin(10.0 * x / (1.0 * v * v)) * 180.0 / pi;
            long double rg = asin(min((long double)1.0, 10.0 * y / (1.0 * v * v))) * 180.0 / pi;
            long double llf = 180.0 - rg, rrg = 180.0 - lf;
            lf /= 2, rg /= 2;
            llf /= 2, rrg /= 2;
            long double total = get(lf, rg, l, r) + get(llf, rrg, l, r);
            cout << 1.0 * total / (r - l) << endl;
        }
    }
    return 0;
}