Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- #include <stdbool.h>
- #define MAXN 100100
- #define EPS 0.000001
- int compare (const void * a, const void * b) {
- if ( *(double*)a < *(double*)b )
- return -1;
- else if ( *(double*)a == *(double*)b )
- return 0;
- else
- return 1;
- }
- double area( double vec[MAXN], int n, double cut ) {
- int i;
- double a = 0.0;
- for ( i = 0; i < n; i++ ) {
- if ( cut < vec[i] )
- a += vec[i]-cut;
- }
- return a;
- }
- int main() {
- double H[MAXN], a;
- int n;
- while ( scanf("%d%lf", &n, &a), n != 0 ) {
- bool done = false;
- int i, h;
- double areaTotal = 0;
- for ( i = 0; i < n; i++ ) {
- scanf("%lf", &h);
- H[i] = h;
- areaTotal += h;
- }
- if ( areaTotal == a ) {
- printf(":D\n");
- continue;
- }
- else if ( areaTotal < a ) {
- printf("-.-\n");
- continue;
- }
- qsort( H, n, sizeof(int), compare );
- double cut;
- double start = H[0], end = H[n-1];
- while ( !done ) {
- cut = ( start + end )/2;
- double cutArea = area( H, n, cut );
- if ( cutArea < a ) {
- start = cut;
- }
- else if ( cutArea > a ){
- end = cut;
- }
- else if ( (end - start) < EPS ) {
- done = true;
- }
- }
- printf("%.4lf\n", cut);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement