Hi, Today I've faced an interesting geometry problem, which I don't know yet how to solve without TLE.
I'm not posting the link because it's in portuguese, but summarising, there's two points in the cartesian plan, the statement gives it's cordinates, how many 'crossing' (integer cordinates) this segments passes through ?
My approach (TLE) O(N) being N the number of integer x cordinates. I check the slope the line, and iterate over the integer point in the x axis and go checking if the current y value for the actual x is also an integer.
The correct solution is probably an formula which easiely check this points in O(1), there's exists this formula ? what's the correct approach ?
Thanks in advance.
Consider the points (x1, y1) and (x2, y2). Let a = |x1 - x2|, b = |y1 - y2|. Then the number of points with integer coordinates on the segment is gcd(a, b) + 1, including points (x1, y1) and (x2, y2).
And one problem: http://acm.timus.ru/problem.aspx?space=1&num=1139
Interesting, thank you so much, but even drawing it in a paper I didn't understood the logic behing it. where's can I seen and detailed explanation about it ?
I don't know, I understood the logic exactly when I drew the picture on the paper :)
Now I've got the idea behind the gcd, it's the maximum integer cordinates of x and y axis isn't it ? but for what the +1 stands about ?
I think, it can be proved using equation of line (ax + by + c = 0).
so all integer solutions can be depended on one parameter:
x = x0 + b/gcd(a,b) * t, y = y0 — a/gcd(a,b) * t (x0 and y0 is some integer solution)
search for "Extended Euclid algorithm"
Segment is all integer solutions in interval [t1 .. t2])) answer is t2 — t1 + 1
good luck
Thank you, nice explanation.. I'm looking for 'Extended Euclid Algorithm' in the net.
it is an ancient and famous problem — linear diophantine equation
I think it should be gcd(a,b)-1 and still I don't know how does this expression come?
Obviously that all integer points split segment into several subsegments. Easy to see that maximum amount of this subsegments is gcd(a,b). So, there is gcd(a,b)-1 points inside the segment +2 ending points. Summary, it is gcd(a,b)+1. Sorry for poor English :)
Oh now I got it. Thanks. No need to apologize if you can convey what you want to say then its perfect. Thanks. :)
gcd(a,b)-1 is excluding the starting and ending points of the line segment .
What if the coordinates of ending points of segment are float?..
Find the subsegment with integer coordinates
Is there any way to find an integral point on a line segment between two given integral points?