fork download
  1. import java.util.*;
  2. public class Main {
  3. private static final int LIM = 20;
  4. public static void main(String[] args) {
  5. final Scanner sc = new Scanner(System.in);
  6. while(sc.hasNext()) {
  7. final int r = sc.nextInt();
  8. final int n = sc.nextInt();
  9. if(r == 0 && n == 0)
  10. return;
  11. final int[] xl = new int[n];
  12. final int[] xr = new int[n];
  13. final int[] h = new int[n];
  14. for(int i = 0; i < n; i++) {
  15. xl[i] = sc.nextInt();
  16. xr[i] = sc.nextInt();
  17. h[i] = sc.nextInt();
  18. }
  19. final int[] hmax = new int[2 * LIM];
  20. for(int i = 0; i < n; i++)
  21. for(int j = xl[i]; j < xr[i]; j++)
  22. hmax[j+LIM] = Math.max(hmax[j+LIM], h[i]);
  23. for(int i = -LIM; i < LIM; i++)
  24. if(hmax[i+LIM] == Integer.MAX_VALUE)
  25. hmax[i+LIM] = 0;
  26. double ans = Double.POSITIVE_INFINITY;
  27. for(int i = -r; i < r; i++) {
  28. final int x = i < 0 ? ~i : i;
  29. ans = Math.min(ans, hmax[i+LIM] + r - Math.sqrt(r * r - x * x));
  30. }
  31. System.out.println(ans);
  32. }
  33. }
  34. }
  35.  
Success #stdin #stdout 0.11s 380672KB
stdin
2 3
-2 -1 3
0 1 3
2 3 3
2 2
-2 0 4
0 2 3
2 6
-3 3 1
-2 3 2
-1 3 3
0 3 4
1 3 5
2 3 6
2 6
-3 3 1
-3 2 2
-3 1 3
-3 0 4
-3 -1 5
-3 -2 6
0 0
stdout
0.0
3.0
2.267949192431123
2.267949192431123