Click here to Skip to main content
16,015,756 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
Hello I have code from an assignment shady park. I have to find a binary search for an angle triangle in C.

4 10 25
0 1
2 3
8 3
10 1
70.346170 109.653830
Process returned 0 (0x0) execution time : 15.147 s
Press any key to continue.

3 5 50
0 1
4 2
5 1
50.194430 146.309930
Process returned 0 (0x0) execution time : 17.072 s
Press any key to continue.

the decimals are supposed to be 70.34618 and 109.65382 instead of the decimals I have the second output. The decimals are supposed to be 50.19443 and 146.30993 instead of the decimals I have for the first output. How I can fix that?

What I have tried:

#include <math.h>
#include <stdio.h>

int main() {
  int n, length, minReqShade;
  scanf("%d%d%d", &n, &length, &minReqShade);

  float towers[n], pos[n];
  for (int i = 0; i < n; ++i)
    scanf("%f%f", &pos[i], &towers[i]);
  /*Here I have created two arrays, towers and position.
  towers will contain height of each tower and pos will contain their respective position.*/


  int low = 0, high = 9000000, ans = 0;


  /*Here for finding the acute angle of sun, I have taken the angle from 0 to 90.
  Since we cannot perform binary search on decimal numbers so I have taken a large number
  Keeping in mind the precision which is 5 digits and at the last I will divide it by 100000 
  to make it in range of 0-90. in ans variable I will store the answer*/


  while (low <= high) {
    int mid = (low + high) / 2;
    float shadow[n]; // The shadow array will contain the end point of the shadow created by ith tower.

    for (int i = 0; i < n; ++i) {
      shadow[i] =
          pos[i] - (towers[i] / tan(((float)mid * M_PI) / (180.0 * 100000.0)));
      if (shadow[i] < 0)
        shadow[i] = 0;
    }
  /* The coverLength variable will store the total shady space in the park.
  start variable will contain the start of the shadow from the ith tower
  ans end variable will contain end of each shadow by ith tower.*/

    float coveredLength = 0, start = pos[n - 1], end = shadow[n - 1];
    for (int i = n - 2; i >= 0; --i) {
      if (pos[i] < end) {
        coveredLength += (start - end);
        start = pos[i];
        end = shadow[i];
      } else {
        end = shadow[i];
      }
    }
  /* Two cases are possible. First is that the shadow ends before the starting of new tower
  and second it ends after new tower. In first case we will direct add computed covered lenght.
  In second case if the shadow goes beyond the end points of the new tower's shadow we will ignore
  the new towers shadow othwrwise we will add new tower shadow .*/

    coveredLength += (start - end);
    if (length * minReqShade <= coveredLength * 100) {
      low = mid + 1;
      ans = mid;
    } else {
      high = mid - 1;
    }
  }
  /*Here according to binary search algorithm if shadow covered reason is more than required 
  shady reason increase the lower limit to mid else decrease higher limit to mid.*/

  printf("%f ", (float)ans / 100000.0);

  low = 9000000, high = 180 * 100000, ans = 180;
  
  
  /* Similarly we will calculate the sun's obtuse angle.
  Only difference is that the shadow will be in opposite direction.
  So calculation loop of shadow will flow oppositely.*/
  

  while (low <= high) {
    int mid = (low + high) / 2;
    float shadow[n];
    for (int i = 0; i < n; ++i) {
      shadow[i] =
          pos[i] - (towers[i] / tan(((float)mid * M_PI) / (180.0 * 100000.0)));
      if (shadow[i] > length)
        shadow[i] = length;
    }
    float coveredLength = 0, start = pos[0], end = shadow[0];
    for (int i = 1; i < n; ++i) {
      if (pos[i] > end) {
        coveredLength += (end - start);
        start = pos[i];
        end = shadow[i];
      } else {
        end = shadow[i];
      }
    }
    coveredLength += (end - start);
    if (length * minReqShade <= coveredLength * 100) {
      high = mid - 1;
      ans = mid;
    } else {
      low = mid + 1;
    }
  }
  printf("%f ", (float)ans / 100000.0);
}
Posted
Updated 20-Sep-22 15:07pm
Comments
Richard MacCutchan 20-Sep-22 10:45am    
You need to explain what the calculations are supposed to be and what the actual problem is.
omar geda 20-Sep-22 10:47am    
Okay this is the problem.

Given the length of the park, location and heights of vertical towers that can block sun rays, and
the percentage of the park that must be shaded, determine the starting and ending angle of the
sun that causes the park to be too sunny.

Input will begin with a line containing 3 integers, N, L, and P (2 ≤ N ≤ 500,000; 1 ≤ L ≤
1,000,000,000; 1 ≤ P ≤ 100), representing the number of sun-blocking towers, the length of the
park, and the percentage of the park that must be shaded. The following N lines will each
contain a description of a sun-blocking tower.
The sun-blocking tower description will consist of 2 space-separated integers, x, and h (0 ≤ x ≤
L; 1 ≤ h ≤ 1,000,000,000), representing the location from the western most point of the park and
the height of the tower respectively. The towers will be given in increasing order of the location.
No two towers will have the same location. The first tower will always be at location 0, and the
last tower will always be at location L.

Output should contain two space-separated floating point values, S and E, representing the
starting and ending angles of the sun from the eastern horizon in degrees, respectively. Both
values should be rounded to exactly 5 decimal places.
Richard MacCutchan 20-Sep-22 11:38am    
So what you actually have is a mathematics problem. You need to figure out the needed calculations first before you convert them to a program.
omar geda 20-Sep-22 11:50am    
oh okay i see thank you

Compiling does not mean your code is right! :laugh:
Think of the development process as writing an email: compiling successfully means that you wrote the email in the right language - English, rather than German for example - not that the email contained the message you wanted to send.

So now you enter the second stage of development (in reality it's the fourth or fifth, but you'll come to the earlier stages later): Testing and Debugging.

Start by looking at what it does do, and how that differs from what you wanted. This is important, because it give you information as to why it's doing it. For example, if a program is intended to let the user enter a number and it doubles it and prints the answer, then if the input / output was like this:
Input   Expected output    Actual output
  1            2                 1
  2            4                 4
  3            6                 9
  4            8                16
Then it's fairly obvious that the problem is with the bit which doubles it - it's not adding itself to itself, or multiplying it by 2, it's multiplying it by itself and returning the square of the input.
So with that, you can look at the code and it's obvious that it's somewhere here:
C
int Double(int value)
   {
   return value * value;
   }

Once you have an idea what might be going wrong, start using the debugger to find out why. Put a breakpoint on the first line of the method, and run your app. When it reaches the breakpoint, the debugger will stop, and hand control over to you. You can now run your code line-by-line (called "single stepping") and look at (or even change) variable contents as necessary (heck, you can even change the code and try again if you need to).
Think about what each line in the code should do before you execute it, and compare that to what it actually did when you use the "Step over" button to execute each line in turn. Did it do what you expect? If so, move on to the next line.
If not, why not? How does it differ?
Hopefully, that should help you locate which part of that code has a problem, and what the problem is.
This is a skill, and it's one which is well worth developing as it helps you in the real world as well as in development. And like all skills, it only improves by use!
 
Share this answer
 
Comments
omar geda 20-Sep-22 11:50am    
that's right, thank you.
If I read your question correctly, your answers are very close to the correct ones. So here's the thing: floating point arithmetic isn't 100% accurate. Small errors creep in because of rounding. Try using double instead of float. It uses more bits and is therefore more accurate. And what's the definition of M_PI? Make sure that it specifies π to, say, 10 digits.
 
Share this answer
 
Comments
merano99 20-Sep-22 20:09pm    
Improving the imprecision of float simply by replacing it with double is often not enough. Mathematical transformations of trigonometric functions, as well as the "correct" order when calculating often bring improvement. It is also better to multiply first and only then to divide.
Greg Utas 20-Sep-22 20:31pm    
Sure, but it depends on the numbers involved. Multiplying by 1/n is the same as dividing by n.
omar geda 20-Sep-22 20:11pm    
That's right. But, i feel like it has something to do with the range. I'm not sure. I did printf("%0.5f ", (float)ans / 100000.0) and the same thing for the other printf statement.
That scaling factor really doesn't help so I would drop it. You should use "%.5f" for a format string to get five decimal places. You used "%f" and that will give the default value of six. I would use doubles everywhere because it is more accurate. I use floats only if the code must run on a GPU and even then sometimes I will use doubles if accuracy is more important than performance.

There is a variation of a binary search that you can use for this problem known as Newton's method - Wikipedia[^] or the Newton-Raphson method. What you do is make two guesses then you do successive interpolations between the answers and guesses until you get a value that is deemed close enough which for you is within 0.00001. You don't necessarily have to use that method but it is one option you can try.
 
Share this answer
 
v2
Comments
omar geda 21-Sep-22 16:48pm    
oh okay good suggestion i changed the floats to doubles , but it gave me :

70.34618 and 109.65383 instead of 109.65382. I'm just wondering how I can do that?
Rick York 21-Sep-22 23:55pm    
In my opinion, the issue is your answer value is an integer and you are scaling by 100000 which is exactly the precision your problem requires. That means you are within one of it so it could be something as simple as a rounding issue. Try making the scale factor 1,000,000 and see how close you get.

Note how many places you will have to change numbers. That is why things like this scaling factor should be definitions or constants so you only have to change one value.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900