You've not done much yet. This isn't as difficult as it looks; there are several things you need to do, so break it down into tasks and debug as you go along.

Quote:
The programm should works as follows :
Great, so you've been given the outline. That saves a lot of bother and gives you some assumptions you can work with.

Quote:
1) we should read the data from the program route.dat, the first line has the coordinates of the driver,
the second line has the coordinates of the destination, the third line has the number of the blocks,nobst (an integer).
The next nobst lines have the coordinates of the center of each circle block and its radius. The blocks are maximum 20.
OK, so as a starting point you can write a program that reads the file and displays what it has found, with relevant labels. This way you can be sure you've understood the data format.
So the data you've given as an example might result in the following output:
Driver drives from (0.0, 10.0) to (15.0, 0.0)
There are 4 blocks
Block 1 is at (2.0, 7.5) and has radius 1.75
Block 2 is at (3.0, 3.0) and has radius 1.0
Block 3 is at (7.0, 5.0) and has radius 2.0
Block 4 is at (12.0, 1.7) and has radius 1.5

Quote:
We also suppose that :
i) xs<xt, so the line which connects the start point and the last point is not vertical and the the start point is always at the left of the finish one
Great, so we can use "easy" maths like y=mx+c, which is prone to infinities when lines are vertical. It's easier than the kind of maths that doesn't have that problem.
Always worth validating the data before proceeding though, just in case the test data has some wrong data.

Quote:
ii) the circle blocks are not intersected
That will also make the program easier; again it's worth checking, if you want. (You might get extra marks)

Quote:
iii) the x-coordinate cx of the center of each circle satisfies xs<cx<xt
Again, this makes the program easier and could be checked for possible extra credit.

Quote:
iv) the line L which connects the start point and the finish point does not necessarily intersects all the circle blocks
So what you'll need is an algorithm to determine the zero, one or two points where a line L intersects a circle. This should be easy enough to find; just Google it (try "line intersects circle").
If zero then you can ignore that circle.
If 1 then you can also ignore the circle because L is tangential to it and no deviation is necessary.

If 2 then you'll need to work out which is the shorter arc. Do you have any idea how to do that? (Hint: try drawing it out on paper and see if you can see anything that might help you centre on a solution).
shabbir like this