10263 - Railway

All about problems in Volume 102. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10263 - Railway

Post by Revenger » Fri Aug 08, 2003 10:10 am

This problem seems to be so easy, but I'm getting WA :cry:

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
Readln(M.x);
Readln(M.y);
Readln(N);
Readln(Rp.x);
Readln(Rp.y);
S := Rp;
for i := 1 to N do begin
Readln(R.x);
Readln(R.y);
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]

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Sun Aug 10, 2003 12:51 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

:(

Post by Revenger » Sun Aug 10, 2003 9:11 pm

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
Readln(M.x);
Readln(M.y);
Readln(N);
Readln(Rp.x);
Readln(Rp.y);
S := Rp;
for i := 1 to N do begin
Readln(R.x);
Readln(R.y);
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!

Post by Revenger » Sun Aug 10, 2003 9:14 pm

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!!!

Post by davor » Sun Aug 31, 2003 1:11 pm

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
   read(px,py);
   read(n);
   rj:=9999999999;
   read(pox,poy);
   rj:=ud(px,py,pox,poy); rx:=pox; ry:=poy;
   for i:=1 to n do begin
       read(krx,kry);
       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
Location: Bangladesh

Precision error.

Post by Rajib » Thu Feb 17, 2005 10:26 am

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. :D
Also becareful with the inputs. Coordinates can be in floating point num:
It may help you...

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
Location: Bangladesh
Contact:

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

Post by TISARKER » Thu Nov 17, 2005 8:30 pm

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
Location: Calgary, Canada

Post by Darko » Tue Jan 10, 2006 8:49 pm

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
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sun Jul 09, 2006 2:29 am

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
Location: Calgary, Canada

Post by Darko » Sun Jul 09, 2006 10:38 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

Post by pplonski » Sun Aug 30, 2009 12:33 am

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

Post by Rafa3p » Wed Jan 04, 2012 8:15 am

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

Post by Beliji » Tue Apr 24, 2012 11:33 pm

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

Post by Repon kumar Roy » Thu Jan 01, 2015 3:11 pm

My Program outputs The same as Jan
But WA's
Here is my code :(
http://ideone.com/VoYlSF

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 10263 - Railway

Post by lighted » Sat Jan 03, 2015 11:21 am

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

Post Reply

Return to “Volume 102 (10200-10299)”