求线段上格点的个数并输出格点

什么是格点：

格点是指横纵坐标均为整数的点。

 

题目描述：

给定平面上的两个格点P1=(x1,y1)和P2=(x2,y2)，线段P1P2上，除了P1和P2以外，一共有几个格点

样例输入：

1 11
5 3

样例输出：

2 9
3 7
4 5
3

 

题目分析：

我们用辗转相除法求最大公约数。
求哪两个数的最大公约数？
两点横坐标的距离和两点纵坐标的距离。然后再用这两个距离除以最大公约数。
为什么要这么做？
有了两个距离的最大公约数，我们就可以把横纵距离均匀的分开。分出来之后，就会保证这些点在这条直线上。

 

用C实现：

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

//定义递归函数，辗转相除法求最大公约数
int gcd(int a,int b){
	if(b==0) return a;
	return gcd(b,a%b);
}

int main(int argc, char *argv[]) {
	int x1,x2,y1,y2,count=0;
	printf("请输入第一个坐标(用空格隔开)：");
	scanf("%d %d",&x1,&y1);
	printf("请输入第二个坐标(用空格隔开)：");
	scanf("%d %d",&x2,&y2);
	
	int g=gcd(abs(x1-x2),abs(y1-y2));
	int b=abs(x1-x2)/g;
	int c=abs(y1-y2)/g;
	
	//前两个while，是直线斜率负的情况，只不过两端点的输入顺序不同，导致大小不同
	while(x1>x2 && y1>y2){
		x1-=b;
		y1-=c;
		if(x1>x2 && y1>y2){
			printf("%d %d\n",x1,y1);
			count++;
		}
	}
	
	while(x1<x2 && y1<y2){
		x1+=b;
		y1+=c;
		if(x1<x2 && y1<y2){
			printf("%d %d\n",x1,y1);
			count++;
		}
	}

	//接下来两个while，是直线斜率为正的情况，输入顺序不同，导致大小不同
	while(x1<x2 && y1>y2){
		x1+=b;
		y1-=c;
		if(x1<x2 && y1>y2){
			printf("%d %d\n",x1,y1);
			count++;
		}
	}
	
	while(x1>x2 && y1<y2){
		x1-=b;
		y1+=c;
		if(x1>x2 && y1<y2){
			printf("%d %d\n",x1,y1);
			count++;
		}
	}
	
	//该while表示斜率为垂直的情况
	while(x1==x2 && y1!=y2){
		if(y1>y2){
			y1-=c;
			if(y1>y2){
				printf("%d %d\n",x1,y1);
				count++;
			}	
		}
		if(y1<y2){
			y1+=c;
			if(y1<y2){
				printf("%d %d\n",x1,y1);
				count++;
			}
		}
	}
	
	printf("%d",count);
	
	return 0;
}

分析代码后，我们不难看出这几个while循环只能进行一个。
所以我们的代码就是把直线情况列举了出来，从而解决不同情况下的问题。