C++中两点之间整数点的个数

在本教程中，我们将编写一个程序来查找给定两点之间整数点的个数。

给定两点之间的点数将为 gcd(abs(x2), abs(y1-y2)) - 1。

如果连接线平行于x轴，则整数点的个数为 abs(y1 - y2) - 1。

如果连接线平行于y轴，则整数点的个数为 abs(x1 - x2) - 1

如果两点的x坐标相等，则它们平行于x轴。如果两点的y坐标相等，则它们平行于y轴。

让我们来看一个例子。

输入

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

输出

1

算法

  • 初始化两点。
  • 检查它们是否平行于x轴。
  • 如果它们平行于x轴，则使用公式 abs(y1 - y2) - 1。
  • 检查它们是否平行于y轴。
  • 如果它们平行于y轴，则使用公式 abs(x1 - x2) - 1。
  • 如果它们不平行于任何轴，则使用公式 gcd(abs(x1-x2), abs(y1- y2)) - 1。
  • 计算结果并打印。

实现

以下是上述算法在C++中的实现

Open Compiler
#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;
}

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

输出

如果运行以上代码，则将得到以下结果。

8

更新于：2021年10月26日

483 次浏览

开启你的职业生涯

通过完成课程获得认证

开始学习
广告