Advertisement
Guest User

Untitled

a guest
Jun 23rd, 2017
52
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.48 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <stdbool.h>
  4.  
  5. #define MAXN 100100
  6. #define EPS 0.000001
  7.  
  8. int compare (const void * a, const void * b) {
  9. if ( *(double*)a < *(double*)b )
  10. return -1;
  11. else if ( *(double*)a == *(double*)b )
  12. return 0;
  13. else
  14. return 1;
  15. }
  16.  
  17. double area( double vec[MAXN], int n, double cut ) {
  18.  
  19. int i;
  20. double a = 0.0;
  21.  
  22. for ( i = 0; i < n; i++ ) {
  23. if ( cut < vec[i] )
  24. a += vec[i]-cut;
  25. }
  26.  
  27. return a;
  28. }
  29.  
  30. int main() {
  31.  
  32. double H[MAXN], a;
  33. int n;
  34.  
  35. while ( scanf("%d%lf", &n, &a), n != 0 ) {
  36.  
  37. bool done = false;
  38. int i, h;
  39. double areaTotal = 0;
  40.  
  41. for ( i = 0; i < n; i++ ) {
  42. scanf("%lf", &h);
  43. H[i] = h;
  44. areaTotal += h;
  45. }
  46.  
  47. if ( areaTotal == a ) {
  48. printf(":D\n");
  49. continue;
  50. }
  51. else if ( areaTotal < a ) {
  52. printf("-.-\n");
  53. continue;
  54. }
  55.  
  56. qsort( H, n, sizeof(int), compare );
  57.  
  58. double cut;
  59. double start = H[0], end = H[n-1];
  60.  
  61. while ( !done ) {
  62.  
  63. cut = ( start + end )/2;
  64. double cutArea = area( H, n, cut );
  65.  
  66. if ( cutArea < a ) {
  67. start = cut;
  68. }
  69. else if ( cutArea > a ){
  70. end = cut;
  71. }
  72. else if ( (end - start) < EPS ) {
  73. done = true;
  74. }
  75. }
  76.  
  77. printf("%.4lf\n", cut);
  78. }
  79.  
  80. return 0;
  81. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement