OJ Board

Posted: **Fri Aug 08, 2003 10:10 am**

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

Posted: **Sun Aug 10, 2003 12:51 pm**

Your program crashes on input like:

Code: Select all

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).

Posted: **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]

Posted: **Sun Aug 10, 2003 9:14 pm**

Thanks, thanks. thanks !

Now, I've fixed all my bugs and get Accepted

Posted: **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]

Posted: **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.

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.

Posted: **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.

Posted: **Tue Jan 10, 2006 8:49 pm**

Can someone with AC check this I/O:

Code: Select all

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

Posted: **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.

Posted: **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...

Posted: **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

Posted: **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;
}

Posted: **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.

Posted: **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

Posted: **Sat Jan 03, 2015 11:21 am**

Your code is ok. Just remove "+ EPS" in two places. (In function slope and Dist)

OJ Board

10263 - Railway

10263 - Railway

:(

Yes!

10263 W.A. plz help me!!!

Precision error.

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

Re: 10263 - Railway

10263 - Railway

Re: 10263 - Railway

Re: 10263 - Railway

Re: 10263 - Railway