Let's look at the case ~n = 1~. Let ~f(x)~ be the area of the flag with height ~x~. It follows ~f(x) = x \sqrt{r^2-x^2}~. The function is increasing until ~x = \frac{r}{\sqrt 2}~ and decreasing afterwards. It follows for ~x < \frac{r}{\sqrt 2}~ the solution is ~f(x)~ and for ~x \ge \frac{r}{\sqrt 2}~ the solution is ~\frac{r^2}{4}~. Notice:

$$\displaystyle f'(x) = \sqrt{r^2-x^2}-\frac{x^2}{\sqrt{r^2-x^2}}$$

Now for the general case. The function ~f(x, r)~ will be analogous to the previous but for any ~r~. Notice that the function ~f'(x)~ is decreasing on the interval ~(0, \frac{r}{\sqrt 2})~. If we were solving the discrete version, it would be enough to always take the element which would increase our solution the most, the correctness of this algorithm relies on the fact that the discrete derivative is decreasing. In the continuous case, the analogous solution is to always move the point which currently has the largest derivative. But, it is easier to fix a derivative ~t~ and check whether the sum of ~x_i~'s such that ~f'(x_i, r_i) = t~ is smaller than ~S~. Notice that for such ~x_i~:

$$\displaystyle x_i = \sqrt{\frac{4r_i^2-t^2-\sqrt{(t^2-4r_i^2)^2-16(r_i^4-t^2 r_i^2)}}{8}}$$

Now it is enough to find such a ~t~ with binary search. It is enough to do ~100~ steps for the wanted precision. The final complexity is ~\mathcal O(100n)~. There are some edge cases that need to be checked by hand.