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 1492. Vasya's Dad 2

Did anybody have troubles with test#5 ?
Posted by Krayev Alexey (PSU) 23 Oct 2006 23:23
Re: Did anybody have troubles with test#5 ?
Posted by Krayev Alexey (PSU) 24 Oct 2006 17:09
Consider test:
3
-15000 0
-14999 0
15000 1

is the output

Yes
-15000.000000 0.500000
-14999.000000 0.499983
14999.000000 0.499983
15000.000000 0.500000
-15000.000000 -0.500000
-14999.000000 -0.499983
14999.000000 0.499983
15000.000000 0.500000

correct ?

I mean if we output only 4 digits it turns into

Yes
-15000.0000 0.5000
-14999.0000 0.5000
14999.0000 0.5000
15000.0000 0.5000
-15000.0000 -0.5000
-14999.0000 -0.5000
14999.0000 0.5000
15000.0000 0.5000
Re: Did anybody have troubles with test#5 ?
Posted by [Ural SU] GetTester 25 Oct 2006 13:19
Yes. Both outputs are correct.
Re: Did anybody have troubles with test#5 ?
Posted by Vedernikoff Sergey 25 Oct 2006 14:29
Really mysterious test...

I can't find error in my program too...
Re: Did anybody have troubles with test#5 ?
Posted by Vedernikoff Sergey 25 Oct 2006 17:27
Oh! What's a bug! The following test helped me to fix it:

Sample input:
7
-5 2
-4 1
-3 -1
-2 -4
-1 -6
0 -7
5 0

Sample output:
Yes
-5 1.0
-4 -0.2
-3 -1.9
-2 -4.1
-1 -5.8
0 -7.0
1 -5.8
2 -4.1
3 -1.9
4 -0.2
5 1.0
-5 1.0
-4 1.2
-3 0.9
-2 0.1
-1 -0.2
1 0.2
2 -0.1
3 -0.9
4 -1.2
5 -1.0
Re: Did anybody have troubles with test#5 ?
Posted by Krayev Alexey (PSU) 25 Oct 2006 23:29
My program passes this test but still wa5
Re: Did anybody have troubles with test#5 ?
Posted by svr 26 Oct 2006 00:24
Friens!. I had no problems with 1492 because used module of fracrion numbers(1274) or in other word used exact arithmetics. Dont use rouunding , epsilon but just exact type.
Re: Did anybody have troubles with test#5 ?
Posted by Krayev Alexey (PSU) 26 Oct 2006 00:53
I use exact arithmetics.
Re: Did anybody have troubles with test#5 ?
Posted by svr 26 Oct 2006 08:46
Then troubles owing to too complicated cod. Problem 1492 is for youngsters. Bounds 15000 are very small and may be worked with by using array F[30000] of fractions. For founding corner point x2 it may be used simplest idea of sliding triple (x-1,y1),(x,y2),(x+1,y) with checking y2*2==y1+y2
Re: Did anybody have troubles with test#5 ?
Posted by Vedernikoff Sergey 27 Oct 2006 15:54
I used real arithmetics, and got AC. My be, it is overflow when use exact arithmetics? In any case, problem can be accepted in both cases.

Edited by author 22.06.2007 14:05
Re: Did anybody have troubles with test#5 ?
Posted by svr 27 Oct 2006 17:05
In our case we form fraction value
F(t)=y[i]+(t-x[i])*(y[i+1]-y[i])/(x[i+1]-x[i])
for t in [x[i];x[i+1]] and after that form
F1[t]=(F[t]+F[-t])/2 and F2[t]=(F[t]-F[-t])/2
t  in [x[0],-x[0]].
Denumenator and numenator dosn't more than 30000*30000=
900000000 . By using __int64 as fraction components
we will in safety  from overflow
Re: Did anybody have troubles with test#5 ?
Posted by [Ural SU] GetTester 28 Oct 2006 23:26
It is not the truth. It is possible to do it without exact arithmetics. The author's decision works without it.
Re: Did anybody have troubles with test#5 ?
Posted by svr 29 Oct 2006 00:37
Wu mustn't repeat author solution. But when we use exact arithmetic we can formulate a problem as some statement on finite set and answer will definite and under control
Re: Did anybody have troubles with test#5 ?
Posted by Azrail 28 Dec 2006 12:31
I used cpp double and eps=1e-9 and got WA5. When i changed eps to 1e-6 i got AC. Maybe it'll helps you.
Re: Did anybody have troubles with test#5 ?
Posted by xiaomengxian 21 Apr 2007 07:28
I used pascal extended and eps=1e-6 and got WA 12. When I changed eps to 1e-9 I got AC... How strange...
Re: Did anybody have troubles with test#5 ?
Posted by AlexF [USTU] 14 Jun 2007 23:21
My eps in cpp double is 1e-9 - AC
Re: Did anybody have troubles with test#5 ?
Posted by pperm 19 Aug 2007 23:58
I have trouble)) I use exact arithmetics and get AC.
Me help test:
5
-3 4
-1 3
0 2
1 1
3 0

Yes
-3.0000 2.0000
3.0000 2.0000
-3.0000 2.0000
-1.0000 1.0000
1.0000 -1.0000
3.0000 -2.0000
Re: Did anybody have troubles with test#5 ?
Posted by Denis Koshman 19 Aug 2008 19:28
Thanks, helped me to find a bug :) I wrote 0 if original function does not cross (0;0). Also I had some problems inside finding mid-point, including X=0 case.

Edited by author 19.08.2008 19:46
Re: Did anybody have troubles with test#5 ?
Posted by bsu.mmf.team 5 Feb 2013 20:24
Solved without exact arithmetic or eps.
Just replace all divisions by multiplications :)

Edited by author 05.02.2013 20:25