a tricky program

Discussion in 'C++' started by sadam, Apr 21, 2011.

  1. sadam

    sadam New Member

    Joined:
    Apr 21, 2011
    Messages:
    33
    Likes Received:
    0
    Trophy Points:
    0
    I'm having a problem with a program in C and i would appreciate if anyone could helped me.

    In this program we have to help a driver reach his destination, from (xs,ys) to (xt,yt). The problem is that his movement across the line L which connects the 2 points is blocked by circles blocks. So when the driver reaches each of this blocks he has to drive to the side of the smallest arc from the two arcs which the line L separates the circle bock, and then continue his movement on line L.

    The programm should works as follows :
    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.
    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
    ii) the circle blocks are not intersected
    iii) the x-coordinate cx of the center of each circle satisfies xs<cx<xt
    iv) the line L which connects the start point and the finish point does not necessarily intersects all the circle blocks

    2) the output of the program should consists of only one line with the command
    printf(”%f\n”, dist); where dist is the distance from the start point and the finish point

    3) the math part of this program is about the arc length and the chord length. If d is the distance from the center of a circle block to the line which connects the start point and the finish point then cosu=d/r, so u=cos^-1(d/r). The arc length is given from s=r.u.
    Finally a line intersects a circle if the distance of the center of the circle to the line is smaller than the radius of the circle

    4) we can use this data for the route.dat:
    0.0 10.0
    15.0 0.0
    4
    2.0 7.5 1.75
    3.0 3.0 1.0
    7.0 5.0 2.0
    12.0 1.7 1.5


    So far i have done this:

    Code:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <math.t>
    
    struct point {
    double x;
    double y;
    };
    
    struct line {
    double a; /* Slope */
    double b; /* y-intercept */
    };
    
    struct circle {
    double cx, cy; /* Center coordinates */
    double r;        /* Circle radius */
    };
    
    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" );
            exit(1);
            }
        fscanf( file, "%lf %lf", &point->x, &point->y );
        fscanf( file, "%lf %lf", &point->x, &point->y );
        fscanf( file, "%d", nobst );
        for( i = 0; i <*nobst )
        {
            fscanf( file, "%lf %lf %1f", &circle.cx,&circle.cy,&circle.r)
        }
        fclose( file );
    }
    
    /* Distance between two points */
    double PointToPoint(sturct point *p, struct point *q);
    
    /* Distance between a point and a line */
    double PointToLine(struct point *p, struct line *l);
    
    
    
    int main()
    {
        Point x;
        Point y;
        int nobst;
        ReadFile( "route.dat", &x, &y, &nobst );
    } 
    Thank you very much
     
    Last edited by a moderator: Apr 22, 2011
  2. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,009
    Likes Received:
    203
    Trophy Points:
    63
    Occupation:
    Senior Support Engineer
    Location:
    England
    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).
     
    shabbir likes this.
  3. sadam

    sadam New Member

    Joined:
    Apr 21, 2011
    Messages:
    33
    Likes Received:
    0
    Trophy Points:
    0
    I'm really confused right now, how will i use the slope of the line L and how to check which of the two arcs is smaller?
    can you write me something in C to make it easier to understand?
    unfortunately i have been trying for days without any progress and the deadline is nearby :disappoin
     
  4. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,009
    Likes Received:
    203
    Trophy Points:
    63
    Occupation:
    Senior Support Engineer
    Location:
    England
    Probably you're trying to do too much. Split it down into simple tasks, have a go and see how far you get.

    Try what I said. Google for an algorithm - and you might even find code already written - for how to find the two points where a line intersects a circle.

    Have a think about how you might determine which of the two arcs is smaller. Draw it out on some paper and see if you can find an approach that will let you centre (<- that word is a REALLY BIG HINT) on a solution.
     
  5. sadam

    sadam New Member

    Joined:
    Apr 21, 2011
    Messages:
    33
    Likes Received:
    0
    Trophy Points:
    0
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    #define MAXCIRCLES 20
    
    struct point {
    double x;
    double y;
    };
    
    struct line {
    double a; /* Slope */
    double b; /* y-intercept */
    };
    
    struct circle {
    double cx, cy; /* Center coordinates */
    double r; /* Circle radius */
    };
    
    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" );
            exit(1);
            }
        fscanf( file, "%lf %lf", &point->x, &point->y );
        fscanf( file, "%lf %lf", &point->x, &point->y );
        fscanf( file, "%d", nobst );
        for( i = 0; i <*nobst )
        {
            fscanf( file, "%lf %lf %1f", &circle.cx,&circle.cy,&circle.r)
        }
        fclose( file );
    }
    
    /* Distance between two points */
    double PointToPoint(sturct point *p, struct point *q);
    
    /* Distance between a point and a line */
    double PointToLine(struct point *p, struct line *l);
    
    
    
    int main()
    {
        point s;
        point t;
        int nobst;
        circle c[MAXCIRCLES];
        ReadFile( "route.dat", &x, &y, &nobst );
    
        line l;
        point close;
        double d;
        double xray = 0.0;
        double around = 0.0;
        double angle;
        double travel;
        int i;
        double asin(),sqrt();
        double distance();
    
        points_to_line(s,t,&l);
    
        for (i=1; i<=nobst; i++) {
        closes_point(c[i].c,,l,close);
        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;
        printf("f\n",dist);
        }
    
    
    Can you correct it for me? it has many errors but i'm tired trying to solve this.
     
    Last edited by a moderator: Apr 23, 2011
  6. sadam

    sadam New Member

    Joined:
    Apr 21, 2011
    Messages:
    33
    Likes Received:
    0
    Trophy Points:
    0


    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 :
    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];
    return;
    }
    if (fabs(l.a) <= EPSILON) { /* horizontal line */
    p_c[X] = p_in[X];
    p_c[Y] = -(l.c);
    return;
    }
    
    
    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" );
            exit(1);
            }
        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();
    
    points_to_line(s,t,&l);
    
    for (i=1; i<=ncircles; i++) {
    closest_point(c[i].c,l,close);
    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;
    printf("f\n",dist);
    }
     
    Last edited by a moderator: Apr 23, 2011
  7. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,009
    Likes Received:
    203
    Trophy Points:
    63
    Occupation:
    Senior Support Engineer
    Location:
    England
    Try reformatting the code (I use Notepad++ and TextFX). If you do, you'll see you're trying to write embedded functions: closest_point() seems to "contain" distance, ReadFile and so on.

    > double distance(sturct

    What's a "sturct"? Seems you've written loads of code and not tested any of it: don't do that, the scope for errors is massive and it's no wonder you haven't got a clue what's happened. Write a few lines of code at a time - no more than 5-10 at your level (and at my level it's really not that much more) before compiling and testing that you get what you think you should get.

    Start with what I suggested - read the file and check the output is what you would expect. Then add functionality a bit at a time and you should storm through this exercise, once you've found the algorithms for line intersects circle, nearest point to line etc.
     
  8. sadam

    sadam New Member

    Joined:
    Apr 21, 2011
    Messages:
    33
    Likes Received:
    0
    Trophy Points:
    0
    Thanks for your help but that what i have in my mind, although it doesn't work..can you tell me exactly where my wrong is so i would finish this a day?
    thank you once again.
     
  9. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,009
    Likes Received:
    203
    Trophy Points:
    63
    Occupation:
    Senior Support Engineer
    Location:
    England
    What are the first five compiler errors?
    Have you tried taking the "plain English" meaning of those errors? For example, if the error is "missing brace", have you tried looking around the given line for such a problem?
     
  10. sadam

    sadam New Member

    Joined:
    Apr 21, 2011
    Messages:
    33
    Likes Received:
    0
    Trophy Points:
    0
    it writes the same wrong message 3 times, that means that it has 3 errors only or the whole program is wrong??
    can you make it run correctly?
     
  11. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,009
    Likes Received:
    203
    Trophy Points:
    63
    Occupation:
    Senior Support Engineer
    Location:
    England
    What are the supposedly wrong messages? why won't you answer my questions directly?
    I'm the expert and you're the beginner, remember, so maybe I have a clue what I'm asking...just a thought...

    Fact is you have way more than three problems. Your syntax is all over the place.
    You need to follow my first suggestion. Write a SMALL amount of code to start. Then
    get that code working BEFORE you try to go onto anything new. I'm not going to reply again until you
    show evidence of having done that because I'm bored with repeating myself, and you would solve this
    problem a whole lot quicker if you listened to me. I know it feels like a retrograde step to throw all
    this wonderful code away and start over, but it's not really.

    Anyway while I'm here. I'll see what Visual Studio 2010 will do with the code. Get a syntax-highlighting
    editor by the way, it will make your life a LOT easier, and ALWAYS ALWAYS ALWAYS strictly indent code.

    points_to_line() has too many braces
    closest_point() doesn't have enough

    By the way always define a return type. The default is int. Return int if that's what you want, otherwise
    return void, then it's clear what your intention is.

    points_to_line() first argument is wrong. The correct syntax is TYPE<space>VARIABLE.
    You have TYPE<dot>VARIABLE.

    In distance(), p and q are defined as struct point *, i.e. pointer to struct point, but you're
    trying to use local semantics (p.x instead of p->x).

    In point_and_slope_to_line(), p is defined as struct point and you're trying to use array semantics
    to access x and y, i.e. p[x] instead of p.x. Also I've no idea what p_c[X] is meant to mean. Do you
    mean p_c.x? Don't forget C and C++ are case sensitive.

    In closest_point, p_c is defined as point, not point*. Remember the difference between pass by copy and pass
    by reference. This is pass by copy, so if your aim here is to modify the caller's p_c, you need to change
    the definition to point* (and use pointer semantics to access the attributes, e.g. p_c->x.

    In distance(), remember that TYPE FUNCTION_NAME(ARGS)<SEMI-COLON> is a function PROTOTYPE, not a function definition.
    So
    Code:
    double distance(struct point *p, struct point *q);
    {
    
    is wrong.

    Maybe closest_point is missing a brace because you haven't finished writing it yet. It handles vertical and horizontal lines,
    but what about the rest?

    distance() uses automatic semantics not pointer semantics for accessing point's x and y members, i.e. point.x instead of point->y.

    ReadFile doesn't initialise nobst.

    Code:
    points_to_line(s,t,&l);
    
    Great use of meaningless variable names. Take a leaf out of the IOCCC's book and rename all your variables to combinations of
    underscores, letters O and digits 0.
    Code:
    points_to_line(_OO,_O0,&_0O);
    
    is considerably more unreadable than this feeble attempt.

    ncircles is undefined.

    c.c is undefined.

    point_in_box is undefined.

    SO. Abandon this lot, there are so many errors and things wrong with it that rescuing it is going to be harder work than my
    approach. For the very last time, as a starting point you should 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

    Then consider putting the data into data structures. Use consistent naming, and use proper names not one letter characters. You're not programming
    a 1K ZX81 you know, where 1-character variable names were pretty much essential. Then start adding BIT BY BIT, no more than 5-10 lines at a time,
    new functionality. Use lots of printfs so the program displays everything it is doing and why, and you'll be able to debug it from the output.
    Eventually when it's all written you can start removing the printfs so that it displays the required output only.
     
  12. sadam

    sadam New Member

    Joined:
    Apr 21, 2011
    Messages:
    33
    Likes Received:
    0
    Trophy Points:
    0


    Can you do the program for me please? or at least some functions?
     
  13. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,009
    Likes Received:
    203
    Trophy Points:
    63
    Occupation:
    Senior Support Engineer
    Location:
    England
    Sure thing. My consultancy rates are UKP150/hour, minimum one 8-hour day, payable in advance.
     
  14. sadam

    sadam New Member

    Joined:
    Apr 21, 2011
    Messages:
    33
    Likes Received:
    0
    Trophy Points:
    0
    Ok, well let's take the whole program from the beggining. So far it's ok?

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <math.t>
    
    struct point {
    double x;
    double y;
    };
    
    struct line {
    double a; /* Slope */
    double b; /* y-intercept */
    };
    
    struct circle {
    double cx, cy; /* Center coordinates */
    double r;        /* Circle radius */
    };
    
    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" );
            exit(1);
            }
        fscanf( file, "%lf %lf", &point->x, &point->y );
        fscanf( file, "%lf %lf", &point->x, &point->y );
        fscanf( file, "%d", nobst );
        for( i = 0; i <*nobst )
        {
            fscanf( file, "%lf %lf %1f", &circle.cx,&circle.cy,&circle.r)
        }
        fclose( file );
    }
    
    /* Distance between two points */
    double PointToPoint(sturct point *p, struct point *q);
    
    /* Distance between a point and a line */
    double PointToLine(struct point *p, struct line *l);
    
    
    
    int main()
    {
        Point x;
        Point y;
        int nobst;
        ReadFile( "route.dat", &x, &y, &nobst );
    }
    
    Are there any other functions that i should include in my program or it's fine?
     
    Last edited by a moderator: Apr 30, 2011
  15. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,009
    Likes Received:
    203
    Trophy Points:
    63
    Occupation:
    Senior Support Engineer
    Location:
    England
    Well, does it work? You don't need me to look over the code before you can determine that. Compile it, if that works, run it and see what output you get. Is it what you expect? If so then it's probably fine.
     
  16. sadam

    sadam New Member

    Joined:
    Apr 21, 2011
    Messages:
    33
    Likes Received:
    0
    Trophy Points:
    0
    well are there any other function i should include in my program or it's fine?'
    thank you
     
  17. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,009
    Likes Received:
    203
    Trophy Points:
    63
    Occupation:
    Senior Support Engineer
    Location:
    England
    What output do you get if you run the program?
    What output do you expect to get?
     
  18. sadam

    sadam New Member

    Joined:
    Apr 21, 2011
    Messages:
    33
    Likes Received:
    0
    Trophy Points:
    0
    i don't get anything yet, i expect to get the distance. so there should be another function called distance?
     
  19. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,009
    Likes Received:
    203
    Trophy Points:
    63
    Occupation:
    Senior Support Engineer
    Location:
    England
    You seem to be using this forum as a substitute for doing your own thinking. Analyse the following answer:

    No, you don't need a function called distance. The computer will be able to guess what you want if you just put
    Code:
    cout << distance;
    
     
  20. sadam

    sadam New Member

    Joined:
    Apr 21, 2011
    Messages:
    33
    Likes Received:
    0
    Trophy Points:
    0
    look man, will you help me or not? every answer you have given me confuses me more!! tell me something in C (and not in C++ as you wrote) or just ignore this program
     

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice