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-15
typedef 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 segment
the 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;
}