In C++, count the number of integer points between two points

In this tutorial we will write a program that finds the number of integer points between given two points.

The number of points between two given points will be gcd(abs(x2), abs(y1-y2)) - 1.

If the connecting line is parallel to the x-axis, the number of integer points will be abs(y1 - y2) - 1.

If the connecting line is parallel to the y-axis, the number of integer points will be abs(x1 - x2) - 1.

If the x-coordinates of two points are equal, they are parallel to the x-axis. If the y-coordinates of two points are equal, they are parallel to the y-axis.

Let's look at an example.

Input

pointOne = [1, 5]
pointTwo = [1, 3]

Output

1

Algorithm

• Initialize two points.
• Check if they are parallel to the x-axis.
• If they are parallel to the x-axis, use the formula abs(y1 - y2) - 1.
• Check if they are parallel to the y-axis.
• If they are parallel to the y-axis, use the formula abs(x1 - x2) - 1.
• If they are not parallel to any axis, use the formula gcd(abs(x1-x2), abs(y1- y2)) - 1.
• Calculate the result and print it.

Implementation

The following is the implementation of the above algorithm in C

#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b) {
   if (b == 0) {
      return a;
   }
   return gcd(b, a % b);
}
int getCount(int pointOne[], int pointTwo[]) {
   if (pointOne[0] == pointTwo[0]) {
      return abs(pointOne[1] - pointTwo[1]) - 1;
   }
   if (pointOne[1] == pointTwo[1]) {
      return abs(pointOne[0] - pointTwo[0]) - 1;
   }
   return gcd(abs(pointOne[0] - pointTwo[0]), abs(pointOne[1] - pointTwo[1])) - 1;
}
int main() {
   int pointOne[] = {1, 3}, pointTwo[] = {10, 12};
   cout << getCount(pointOne, pointTwo) << endl;
   return 0;
}

Output

If you run the above code, you will get the following results.

8

The above is the detailed content of In C++, count the number of integer points between two points. For more information, please follow other related articles on the PHP Chinese website!