ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1719. Kill the Shaitan-Boss

Why WA31?
Posted by vgu 24 Oct 2009 14:17
Re: Why WA31?
Posted by Alex Tolstov (Vologda STU) 25 Oct 2009 00:01
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?
Posted by Alex Tolstov (Vologda STU) 26 Oct 2009 16:29
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?
Posted by Alex Tolstov (Vologda STU) 26 Oct 2009 19:03
send me your code, and I'll try to tell you where is your bug:
gm.alext@gmail.com

:)
Re: Why WA31?
Posted by Alex Tolstov (Vologda STU) 27 Oct 2009 23:34
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