Why WA31?

Posted by

vgu 24 Oct 2009 14:17

Re: Why WA31?

What method do you use?

Re: Why WA31?

Posted by

vgu 26 Oct 2009 00:55

I use ternary search.

My C++ solution has wa17 and Pascal solution with extended has wa31. Maybe this because i use sqrt function?

*Edited by author 26.10.2009 00:56*

*Edited by author 26.10.2009 00:56*

Re: Why WA31?

I use ternary search too, sqrt-function, and type double in Java. I don't use epsilon in calculations.

May be, calculations the distance from point to line is not too exact? I use vector product to calc 2*area of a triangle, and then divide it on base to get distance.

Re: Why WA31?

Posted by

vgu 26 Oct 2009 18:48

I use vector product too :(

why wa31 :(

Re: Why WA31?

send me your code, and I'll try to tell you where is your bug:

gm.alext@gmail.com

:)

Re: Why WA31?

I am sure that you have problem with precision.

I tested one of solutions and found that point coordinates on line must be very exact.

One way to get very exact coordinates:

we have two points: a and b.

double factor = value in range from -10000 to 10000

double dx = b.x - a.x;

double dy = b.y - a.y;

double x = a.x + dx * factor;

double y = a.y + dy * factor;

(x, y) - coordinates of point belongs to line, containing a and b.

Re: Why WA31?

Posted by

vgu 28 Oct 2009 16:07

AC now :)

Great thanks to Alex Tolstov