## 10263 - Railway

Moderator: Board moderators

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

### 10263 - Railway

This problem seems to be so easy, but I'm getting WA My algo is simple:
1. For each segment AB do
1.a Check if points A or B can be choosen (It's possible if cos(A) <= 0 or cos(B) <=0))
1.b Else try to find such point X on AB that XM is minimal
1.c Check if the point X that we found is better than points that we found before
2 Output X

Anyway, it gets WA (But I think that my algo is correct)
My program

[pascal]Program p10263; {\$n+}

Const Eps = 1e-7;
Eps2 = 1e-5;

Type Point = Record x, y : Extended End;

Var M, S : Point;
N, i : Integer;
R, Rp : Point;

Function Dist(A, B : Point) : Extended;
begin
Dist := Sqrt(Sqr(A.x - B.x) + Sqr(A.y - B.y));
end;

Function GetCosA(A, B, C : Point) : Extended;
Var la, lb, lc : Extended;
begin
la := Dist(B, C);
lb := Dist(A, C);
lc := Dist(A, B);
GetCosA := (lb * lb + lc * lc - la * la) / 2 / lb / lc;
end;

Function FindMinPoint(A, B, M : Point; Var X : Point) : Extended;
Var cosa, cosb, len : Extended;
TX : Point;
begin
cosa := GetCosA(A, B, M);
cosb := GetCosA(B, A, M);
if (cosa < Eps) Or (cosb < Eps) then begin
if Dist(A, M) < Dist(B, M) then TX := A else TX := B;
if Dist(M, TX) < Dist(M, X) then X := TX;
Exit;
end;
len := Dist(A, M) * cosa;
TX.x := A.x + len / Dist(A, B) * (B.x - A.x);
TX.y := A.y + len / Dist(A, B) * (B.y - A.y);
if Dist(M, TX) < Dist(M, X) then X := TX;
end;

begin
While Not Eof Do begin
S := Rp;
for i := 1 to N do begin
FindMinPoint(R, Rp, M, S);
Rp := R;
end;
if Abs(S.x) > Eps2 then Writeln(S.x:0:4) else Writeln('0.0000');
if Abs(S.y) > Eps2 then Writeln(S.y:0:4) else Writeln('0.0000');
end;
end.[/pascal]
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Your program crashes on input like:

Code: Select all

``````0
0
1
1
1
1
1``````
I don't know if there are such cases in the judges input, but if there are, you'll get WA (and not RTE, that kind of information is not supplied to Pascal programmers).
Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

### :(

Tanks, I fixed it
But I still get WA [pascal]Program p10263; {\$n+}

Const Eps = 1e-7;
Eps2 = 1e-5;

Type Point = Record x, y : Extended End;

Var M, S : Point;
N, i : Integer;
R, Rp : Point;

Function Dist(A, B : Point) : Extended;
begin
Dist := Sqrt(Sqr(A.x - B.x) + Sqr(A.y - B.y));
end;

Function GetCosA(A, B, C : Point) : Extended;
Var la, lb, lc : Extended;
begin
la := Dist(B, C);
lb := Dist(A, C);
lc := Dist(A, B);
GetCosA := (lb * lb + lc * lc - la * la) / 2 / lb / lc;
end;

Function FindMinPoint(A, B, M : Point; Var X : Point) : Extended;
Var cosa, cosb, len : Extended;
TX : Point;
begin
if Dist(A, B) < Eps2 then begin
TX := A;
if Dist(M, TX) < Dist(M, X) then X := TX;
Exit;
end;
cosa := GetCosA(A, B, M);
cosb := GetCosA(B, A, M);
if (cosa < Eps) Or (cosb < Eps) then begin
if Dist(A, M) < Dist(B, M) then TX := A else TX := B;
if Dist(M, TX) < Dist(M, X) then X := TX;
Exit;
end;
len := Dist(A, M) * cosa;
TX.x := A.x + len / Dist(A, B) * (B.x - A.x);
TX.y := A.y + len / Dist(A, B) * (B.y - A.y);
if Dist(M, TX) < Dist(M, X) then X := TX;
end;

begin
While Not Eof Do begin
S := Rp;
for i := 1 to N do begin
FindMinPoint(R, Rp, M, S);
Rp := R;
end;
if Abs(S.x) > Eps2 then Writeln(S.x:0:4) else Writeln('0.0000');
if Abs(S.y) > Eps2 then Writeln(S.y:0:4) else Writeln('0.0000');
end;
end.[/pascal]
Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

### Yes!

Thanks, thanks. thanks ! Now, I've fixed all my bugs and get Accepted
davor
New poster
Posts: 8
Joined: Sat Jun 28, 2003 11:04 pm

### 10263 W.A. plz help me!!!

Can anyone tell me what's wrong with my program? HELP

Code: Select all

``````var i,n:integer;
px,py,krx,kry,kx,ky,pox,poy,rj,rx,ry,srx,sry:extended;

function ud(px,py,kx,ky:extended):extended;
begin
ud:=sqrt(sqr(px-kx)+sqr(py-ky));
end;

function raz(a,b:extended):boolean;
var e:boolean;
a1,b1:real;
begin
e:=true;
if abs(a-b)<0.000001 then e:=false;
raz:=e;
end;

begin
while not eof(input) do begin
rj:=9999999999;
rj:=ud(px,py,pox,poy); rx:=pox; ry:=poy;
for i:=1 to n do begin
kx:=krx; ky:=kry;
while (raz(krx,pox)) or (raz(kry,poy)) do begin
srx:=(krx+pox)/2;
sry:=(kry+poy)/2;
if ud(px,py,pox,poy)<ud(px,py,krx,kry) then begin
krx:=srx; kry:=sry;
end
else begin
pox:=srx; poy:=sry;
end;
end;
if ud(px,py,pox,poy)<rj then begin
rj:=ud(px,py,pox,poy);
rx:=pox; ry:=poy;
end;
pox:=kx; poy:=ky;
end;
writeln(rx:0:4);
writeln(ry:0:4);
end;
end.
[/pascal]``````
Rajib
New poster
Posts: 28
Joined: Tue Nov 04, 2003 6:45 am

### Precision error.

I'm not a pascal progrqammer. Try to shear ideas rather sending codes.
Most people prefer C/C++

But I think you check 1e-6 for precision error.
I got accepted using 1e-10 for prcision error. Also becareful with the inputs. Coordinates can be in floating point num:

A tip if required:
This is a simple binary search problem.
(a) For every segment find the minimum distance point uisng BS.
(b) Update if it is less than previous solution.
TISARKER
Learning poster
Posts: 88
Joined: Tue Oct 12, 2004 6:45 pm
Contact:

### 10263-Railway(Please give me some I/O)

I am getting wrong answer. I checked all possible case as my ability
Please give me some input and output for which my program give wrong output.
Mr. Arithmetic logic Unit
Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Can someone with AC check this I/O:

Code: Select all

``````6
-3
3
0
1
5
5
9
-5
15
3
0
0
1
1
0
2
0
1
1
5
-1
-2
2
-1
3
2
1
3
-1
1
-2
-1
4
4
5
-1
-2
2
-1
3
2
1
3
-1
1
-2
-1
0
0
5
-1
-2
2
-1
3
2
1
3
-1
1
-2
-1
0.5
0.5
5
-1
-2
2
-1
3
2
1
3
-1
1
-2
-1
-0.5
-0.5
5
-1
-2
2
-1
3
2
1
3
-1
1
-2
-1
-2
-2
5
-1
-2
2
-1
3
2
1
3
-1
1
-2
-1
1
-1
5
-1
-2
2
-1
3
2
1
3
-1
1
-2
-1
2
-2
5
-1
-2
2
-1
3
2
1
3
-1
1
-2
-1
2.7654
2.3456
5
-1
-2
2
-1
3
2
1
3
-1
1
-2
-1
-1
-1
5
-1
-2
2
-1
3
2
1
3
-1
1
-2
-1
-2
-2
5
-1
-2
2
-1
3
2
1
3
-1
1
-2
-1
-3
-3
5
-1
-2
2
-1
3
2
1
3
-1
1
-2
-1
``````

Code: Select all

``````7.8966
-2.2414
1.0000
0.0000
0.0000
2.0000
3.0000
2.0000
-1.2000
0.6000
-0.5000
1.5000
-1.5000
0.0000
-2.0000
-1.0000
1.1000
-1.3000
1.7000
-1.1000
2.6741
2.1630
-1.8000
-0.6000
-2.0000
-1.0000
-2.0000
-1.0000
``````
With the given points, the last two cases have 2 correct answers, I just print the last one (the other one is (-1,-2)).

Thanks,
Darko
Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
My Accepted code returns...

Output:

Code: Select all

``````7.8966
-2.2414
1.0000
0.0000
0.0000
2.0000
3.0000
2.0000
-1.2000
0.6000
-0.5000
1.5000
-1.5000
0.0000
-1.0000
-2.0000
1.1000
-1.3000
1.7000
-1.1000
2.6741
2.1630
-1.8000
-0.6000
-1.0000
-2.0000
-1.0000
-2.0000``````
Hope it helps.
Ami ekhono shopno dekhi...
HomePage
Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Thanks, Jan, it did help. But my (now AC) program produces the same output as before, so there might not be those kinds of inputs (no yellow check mark and our outputs are different).

Turned out that it was one of those Java quirks (that I didn't know about at the time I tried it originally). I guess I should go through all of these WAs... pplonski
New poster
Posts: 1
Joined: Mon Aug 24, 2009 12:41 pm

### Re: 10263 - Railway

Hi !

i've got problem with code:

Code: Select all

``````#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <vector>
#include <deque>
#include <math.h>
#include <map>
#include <set>

#define REP(x, n) for(int x = 0; x < (n); ++x)
#define VAR(v, n) __typeof(n) v = (n)
#define SIZE(x) ((int)(x).size())
#define LEN(x) ((int) (x).length())
#define FOREACH(i, c) for(VAR(i, (c).begin()); i !=(c).end(); ++i)
#define PB push_back
#define ST first
#define ND second
#define MP make_pair

using namespace std;

typedef long long LL;

#define Det(a,b,c) (LL(b.x-a.x)*LL(c.y-a.y) - LL(b.y-a.y)*LL(c.x-a.x))
const double EPS = 10e-9;
inline bool IsZero(double x)
{
return x >= -EPS && x <= EPS;
}
struct POINTD
{
double x,y;
POINTD(double wx = 0, double wy = 0) : x(wx), y(wy) {}
bool operator==(POINTD &a)
{
return IsZero(a.x-x) && IsZero(a.y-y);
}
};

ostream& operator<<(ostream &os, POINTD &p)
{
os << "(" << p.x << ", " << p.y << ")" << endl;
}

double sqr(double x) {
return x*x;
}

double abs(double x) {
return (x < 0)? -x : x;
}

double sgn(double x) {
return (x < 0)? -1.0 : 1.0;
}

double Distance(POINTD p1, POINTD p2)
{
double x = sqr(p1.x-p2.x);
double y = sqr(p1.y-p2.y);
return sqrt(x + y);
}

double Cos(POINTD a, POINTD b, POINTD c)
{
double la = Distance(b, c);
double lb = Distance(a, c);
double lc = Distance(a, b);
return (sqr(lb) + sqr(lc) - sqr(la))/2.0/lb/lc;
}

double count(POINTD p1, POINTD p2, POINTD m, POINTD &sol)
{
if(Distance(p1, p2) < EPS)
{
sol = p1;
return Distance(p1, m);
}

double cosa = Cos(p1, p2, m);
double cosb = Cos(p2, p1, m);

if(cosa < EPS || cosb < EPS)
{
double d1 = Distance(p1, m);
double d2 = Distance(p2, m);
if(d1 < d2)
{
sol = p1;
return d1;
}
else
{
sol = p2;
return d2;
}
}

double len = Distance(p1, m) * cosa;

sol.x = p1.x + len / Distance(p1,p2) * (p2.x - p1.x);
sol.y = p1.y + len / Distance(p1,p2) * (p2.y - p1.y);

return Distance(m, sol);
}

int main()
{
while(!cin.eof())
{
POINTD M;
cin >> M.x >> M.y;
int n;
cin >> n;
++n;
POINTD tab[n];
REP(x, n)
cin >> tab[x].x >> tab[x].y;

double min = 10000000000.0;
POINTD p_min;
REP(i, n-1)
{
POINTD s;
double m = count(tab[i], tab[i+1], M, s);
if(m < min) {
min = m;
p_min.x = s.x;
p_min.y = s.y;
}
}
cout.precision(4);
cout.setf(ios::fixed,ios::floatfield);
if(p_min.x < 0.00001 && p_min.x > -0.00001)
p_min.x = 0;
if(p_min.y < 0.00001 && p_min.y > -0.00001)
p_min.y = 0;

cout << p_min.x << endl << p_min.y << endl;
}
return 0;
}

``````
i think i've got alg OK but something wrong is with my IO, could you help?

thanks,
Piotr
Rafa3p
New poster
Posts: 5
Joined: Sun Dec 25, 2011 1:32 am

### 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-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;
}
``````
Beliji
New poster
Posts: 1
Joined: Tue Apr 24, 2012 11:31 pm

### 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.
Repon kumar Roy
Learning poster
Posts: 96
Joined: Tue Apr 23, 2013 12:54 pm

### Re: 10263 - Railway

My Program outputs The same as Jan
But WA's
Here is my code http://ideone.com/VoYlSF
lighted
Guru
Posts: 587
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 10263 - Railway

Your code is ok. Just remove "+ EPS" in two places. (In function slope and Dist)
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman