Generate Uniform Samples and Estimate Percentiles

Part 1: Sampling a Square

You are given a function rand01() that returns a uniform random float in the range [0, 1). Implement a function that returns a pair of coordinates (x, y) representing a uniform random point within a square defined by vertices (0, 0) and (S, S).

Part 2: Percentile Estimation

You are provided with a histogram representing the distribution of a large dataset. The data is grouped into M contiguous bins. You are given:

• bin_edges: A list of M+1 values [e_0, e_1, ..., e_M] where the i-th bin spans [e_i, e_{i+1}).
• bin_counts: A list of M values [c_0, c_1, ..., c_{M-1}] where c_i is the number of observations in the i-th bin.
• p: The target percentile (e.g., 0.95 for the 95th percentile).

Write a function to estimate the value of the p-th percentile using linear interpolation within the appropriate bin.

Example

bin_edges = [0, 10, 20, 30] bin_counts = [100, 200, 100] Target p = 0.50 (Median)

1. Total count = 400. Target rank = 0.50 * 400 = 200.
2. The 200th observation falls within the second bin [10, 20).
3. Use linear interpolation to find the value within the bin.

Constraints

• bin_counts values are non-negative.
• bin_edges are strictly increasing.