How can I fix this problem?

Question

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 20-Sep-22 4:37am

omar geda

Updated 20-Sep-22 15:07pm

Add a Solution

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

3 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

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

OriginalGriff · Answer 1 · 2022-09-20T05:00:00

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!

Greg Utas · Answer 2 · 2022-09-20T07:26:00

Solution 2

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.

Posted 20-Sep-22 7:26am

Greg Utas

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.

Rick York · Answer 3 · 2022-09-20T15:07:00

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.

How can I fix this problem?

3 solutions

Solution 1

Solution 2

Solution 3

Add your solution here

Preview 0