Range overflow in VSN

When we are finding distance b/w P and Q (x2-x1)^2 + (y2-y1)^2 whole underoot.(for 2d case). Now according to constraint of co-ordinates (this value (x2-x1)^2 + (y2-y1)^2) can exceed max value possible to store)?

2 Likes

Its guaranteed that co-ordinates of Q never exceed 2*{10}^{9} during entire time.

1 Like

As specified in the constraints that the absolute value of the coordinates can be at max 2 *10^9 .
Now if we take x2=2 *10^9, x1=-2 *10^9, y2=2 *10^9, y1=-2 *10^9, so it’s pretty clear the value

(x2-x1)^2 + (y2-y1)^2 turns out to be 32 *10^18 which does not fit into long type integers . So yes, it would overflow.

Use long double.

@vijju123 What about JAVA , it can support at max 64 bits

As that is 64 bit then i think it can also store same as c++ upto 2^64-1,thats nearly 18*10^18.

Will double not suffice? Did you try that?

@vijju123 no need to use long double, even for C++ double would suffice.

yeah @vijju123 and @souradeep1999 you are right

Thats true, but long double afaik is more precise than double. I never trust floating points so thought better safe than sorry xD

How can long double store more than 64 bits i.e >10^18

long double or even double can be used. They have a huge range (around 1.7e^{308}) (check here) even though they are 64 bits since they use floating point representation, i.e. have some bits reserved for exponent and some bits for mantissa.