Range overflow in VSN

doubt

#1

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

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.


#3

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


#4

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.


#5

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


#6

Use long double.


#7

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


#8

Will double not suffice? Did you try that?


#9

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


#10

yeah @vijju123 and @souradeep1999 you are right


#11

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


#12

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