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

알고리즘

• 2점을 초기화합니다.
• X축과 평행한지 확인하세요.
• x축과 평행하면 abs(y1 - y2) - 1 공식을 사용하세요.
• y축과 평행한지 확인하세요.
• y축과 평행하면 abs(x1 - x2) - 1 공식을 사용하세요.
• 축과 평행하지 않으면 gcd(abs(x1-x2), abs(y1-y2)) - 1 공식을 사용합니다.
• 결과를 계산하고 인쇄합니다.

구현

다음은 위의 알고리즘을 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;
}

출력

위의 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.

8