## 10263 - Railway

Moderator: Board moderators

### 10263 - Railway

Can somebody give me some help? I don't know y i'm getting WA.
I guess I'm with precision error, bur dont know how to fix it

The Algorithm is that :
For each segment
---Look if M is inside AB line
---If it is -> Choose lesser distance : AM or BM
---Else -> Find the point X in the perpendicular line to AB that pass by M
-----------Look if X is inside AB segment
-----------If it is -> D = X
-----------Else -> Choose lesser distance : AP or BP
Then choose the lesser distance for all segments(using variable min)

Code: Select all
`#include <stdio.h>#include <stdlib.h>#include <float.h>#include <math.h>#define EPS 1e-15typedef struct POINT{    double x,y;} POINT;/*Calculates the distance between two points*/double Distance(POINT *A, POINT *B){    return sqrt((A->x - B->x)*(A->x - B->x) +(A->y - B->y)*(A->y - B->y) );}/*Return 1 if P is in AB line, else return 0*/int IsCollinear(POINT *A, POINT *B,POINT *P){    return (((B->x - A->x)* (P->y - A->y)) ==            ((B->y - A->y)*(P->x - A->x  )));}/*Returns the distance from p and the segmentthe closest point is stored in the 4º parameter*/double DistToSegment(POINT *A, POINT *B,POINT *P, POINT *D){    if(IsCollinear(A,B,P))    {        if(Distance(A,P)>Distance(B,P))        {            *D=*B;            return Distance(B,P);        }        *D=*A;        return Distance(A,P);    }    double m1,m2,b1,b2,x,y;    if(B->x==A->x) /*Avoiding division by zero*/    {        x = A->x;        y = P->y;    }    else   /*Finding the point (x,y), closer to M and in the line made by AB*/    {        m1 = (B->y - A->y)/(B->x - A->x);        b1 = A->y - m1*A->x;        m2 = -1/m1;        b2 = P->y - m2*P->x;        x = (b2-b1)/(m1-m2);        y = m1*x+b1;    }    /*Looking if the point (x,y) is inside the segment AB*/    if( ((x >= A->x) && (x <= B->x) && (y >= A->y) && (y <= B->y)) ||            ((x >= A->x) && (x <= B->x) && (y <= A->y) && (y >= B->y)) ||            ((x <= A->x) && (x >= B->x) && (y >= A->y) && (y <= B->y)) ||            ((x <= A->x) && (x >= B->x) && (y <= A->y) && (y >= B->y)) )    {        D->x=x;        D->y=y;        return Distance(D,P);    }    /*Else, return A or B*/    if(Distance(A,P)>Distance(B,P))    {        *D=*B;        return Distance(B,P);    }    *D=*A;    return Distance(A,P);}int main(void){    int n;    double a,b,min;    POINT p1,p2,p3,p4,M;    while(scanf(" %lf %lf ",&a,&b)!=EOF)    {        min = DBL_MAX;        M.x=a;        M.y=b;        scanf(" %d ",&n);        scanf(" %lf %lf",&a,&b);        p1.x=a;        p1.y=b;        while(n--)        {            scanf(" %lf %lf ",&a,&b);            p2.x=a;            p2.y=b;            a = DistToSegment(&p1,&p2,&M,&p4);            if(a<min)            {                p3 = p4;                min = a;            }            p1=p2;        }        if(p3.x==0)printf("0.0000\n");        else printf("%.4f\n",p3.x);        if(p3.y==0)printf("0.0000\n");        else printf("%.4f\n",p3.y);    }    return 0;}`
Rafa3p
New poster

Posts: 5
Joined: Sun Dec 25, 2011 1:32 am

### Re: 10263 - Railway

To calculate distance between two points you can use google earth. By using google earth you will get the right calculation of distance between two points. Also you an use a good distance calculator to calculate the distance between two points. I think my advices will help you.
Beliji
New poster

Posts: 1
Joined: Tue Apr 24, 2012 11:31 pm