aajjbb's blog

Integer Cordinates in a Segment
By aajjbb, 12 years ago, In English

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.

  • Vote: I like it
  • +1
  • Vote: I do not like it

Comments Comments (14)
| Write comment?
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 ?

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I don't know, I understood the logic exactly when I drew the picture on the paper :)

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 ?

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
          ← Rev. 3   Vote: I like it +5 Vote: I do not like it

          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

          → Reply
          • »
            »
            »
            »
            »
            »
            12 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Thank you, nice explanation.. I'm looking for 'Extended Euclid Algorithm' in the net.

            → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        it is an ancient and famous problem — linear diophantine equation

        → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think it should be gcd(a,b)-1 and still I don't know how does this expression come?

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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 :)

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Oh now I got it. Thanks. No need to apologize if you can convey what you want to say then its perfect. Thanks. :)

        → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      gcd(a,b)-1 is excluding the starting and ending points of the line segment .

      → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What if the coordinates of ending points of segment are float?..

    → Reply
»
7 years ago, # |
← Rev. 4   Vote: I like it -9 Vote: I do not like it

Is there any way to find an integral point on a line segment between two given integral points?

→ Reply