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

Yes. Both outputs are correct.

Really mysterious test...

I can't find error in my program too...

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

My program passes this test but still wa5

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.

I use exact arithmetics.

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

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

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

It is not the truth. It is possible to do it without exact arithmetics. The author's decision works without it.

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

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.

I used pascal extended and eps=1e-6 and got WA 12. When I changed eps to 1e-9 I got AC... How strange...

My eps in cpp double is 1e-9 - AC

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

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

Solved without exact arithmetic or eps.
Just replace all divisions by multiplications :)

Edited by author 05.02.2013 20:25