Originally Posted by xpi0t0s View Post
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.

Great, so you've been given the outline. That saves a lot of bother and gives you some assumptions you can work with.

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

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.

That will also make the program easier; again it's worth checking, if you want. (You might get extra marks)

Again, this makes the program easier and could be checked for possible extra credit.

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).

i have done this so far, i think it's done but it says that it has 3 errors, can you correct them so the program should work?

Code :
#define MAXN 20

typedef struct {
        double cx,cy;;   /* center of circle */
        double r;        /* radius of circle */
        } circle;

struct point {
    double x, y;

typedef struct {
    double a;            /* x-coefficient */
    double b;            /* y-coefficient */
    double c;            /* constant term */
        } line;

points_to_line(point.p1, point p2, line *l)
        if (p1[X] == p2[X]) {
        l->a = 1;
        l->b = 0;
        l->c = -p1[X];
        } else {
        l->b = 1;
        l->a = -(p1[Y]-p2[Y])/(p1[X]-p2[X]);
        l->c = -(l->a * p1[X]) - (l->b * p1[Y]);

point_and_slope_to_line(point p, double m, line *l)
        l->a = -m;
        l->b = 1;
        l->c = -((l->a*p[x]) + (l->b*p[y]));

closest_point(point *p_in, line l, point p_c)
line perp; /* perpendicular to l through (x,y) */
if (fabs(l.b) <= EPSILON) { /* vertical line */
p_c[X] = -(l.c);
p_c[Y] = p_in[Y];
if (fabs(l.a) <= EPSILON) { /* horizontal line */
p_c[X] = p_in[X];
p_c[Y] = -(l.c);

double distance(sturct point *p, struct point *q);
    double d=0.0;

    d = (point.x - point.y) * (point.x - point.y);
    return( sqrt(d) );

void ReadFile( const char *filename, point *x, point *y, int *nobst )
    FILE *file;
    int i;
    if (( file = fopen( filename, "r" )) == NULL )
        printf ( "Error opening file!\n" );
    fscanf( file, "%lf %lf", &s.x, &s.y );
    fscanf( file, "%lf %lf", &t.x, &t.y );
        for( i = 0; i <*nobst; i++)
        fscanf( file, "%lf %lf %1f", &circle.cx,&circle.cy,&circle.r);
    fclose( file );

point s;            /* Superman’s initial position */
point t;            /* target position */
int nobst;       /* number of circles */
circle c[MAXN];     /* circles data structure */

int main()
ReadFile( "route.dat", &s, &t, &nobst );
line l;                 /* line from start to target position */
point close;            /* closest point */
double d;               /* distance from circle-center */
double xray = 0.0;      /* length of intersection with circles */
double around = 0.0;    /* length around circular arcs */
double angle;           /* angle subtended by arc */
double dist;          /* total travel distance */
int i;
double asin(), sqrt();
double distance();


for (i=1; i<=ncircles; i++) {
d = distance(c[i].c,close);
if ((d>=0) && (d < c[i].r) && point_in_box(close,s,t)) {
xray += 2*sqrt(c[i].r*c[i].r - d*d);
angle = acos(d/c[i].r);
around += ((2*angle)/(2*PI)) * (2*PI*c[i].r);
dist = distance(s,t) - xray + around;

Last edited by shabbir; 23Apr2011 at 09:06.. Reason: Code blocks