[数据结构与算法]2021年第十二届蓝桥杯省赛大学B组试题C直线-个人题解

试题题目原题：

本题答案：40257
解题思路：
??一、在平面直角坐标系统XOY中，有点集{(x,y)|0≤x<2,0≤y<3,x ? Z,y ? Z}，确定了2×3=6个点。每两个点都能确定一条直线，那么该六个点就能确定$\left(\genfrac{}{}{0ex}{}{6}{2}\right)$=15条直线，其中包含3条平行于x轴（包含x轴）的直线，2条平行于y轴（包含y轴）的直线。为了保证直线不重复，从第0个点（原点(0,0)）出发，走过的点不再走一遍，每个点都与剩下的点连接。他们分别是

所以点集{(x,y)|0≤x<2,0≤y<3,x ? Z,y ? Z}所连接起来的直线有 6+2+3 = 11 条；

??二、同理，对于再平面直角坐标系统XOY中，点集{(x,y)|0≤x<20,0≤y<21,x ? Z,y ? Z}，可以确定20×21=420个点。420个点能确定$\left(\genfrac{}{}{0ex}{}{420}{2}\right)=87990$条直线。
??使用C语言编写程序，用结构体STOP存储点的坐标，用结构体LINE存储直线的四个元素，A,B,C,value，其中value的值用来去重。STOP定义的结构体数组长度是col×row，结构体LINE定义的结构体数据长度可以假设为100000。
1、计算直线方程的方法：
???根据数学平面几何知识，两点确定一条直线，两点式直线方程表达式为：
$$(y?y_1)/(y_1?y_2)=(x?x_1)/(x_1?x_2)$$
???变形后
$$(y?y_1)(x_1?x_2)=(x?x_1)(y_1?y_2)$$
???再去括弧，移项，得一般形式方程：
$$(y_1?y_2)x+(?(x_1?x_2))y+(x_1?y_2?y_1?x_2)=0$$
???对应于一般式 Ax+By+C = 0 分别是：
$$A=y_1?y_2，B=?(x_1?x_2)=x_2?x_1，C=x_1?y_2?y_1?x_2$$
???其中平行于x轴（包含x轴）直线和平行于y轴（包含y轴）直线，总和就是x轴和y轴上的点是的和，在计算直线方程时，不需要计算这种直线。
???特别注意：需要对A,B,C约分，把 Ax+By+C = 0 化为最简形式，方便去重。

2、去重的方法：
??遍历直线LINE结构体数组，如果两个结构体中A，B，C数据相同，那么就认为这两个直线是重合的直线。第一条直线的不能判断它与哪条直线重合，那么把该直线的value数据赋值为1。从第二条直线开始，与它前面的所有直线作比较，如果前面有与该直线重合的直线，那么该直线的value数据不变，等于前一个直线的value数值；如果前面没有与该直线重合的直线，那么该直线的value数据将在前一个直线的value数值加1。遍历所有的直线后，最后一条直线的value值就是去重后的直线条数。
??注意：最终的直线条数是 最后一条直线的value值 加上 平行于x轴（包含x轴）直线和平行于y轴（包含y轴）直线和。

#include<stdio.h>
#define max 1000000
#define row 21 
#define col 20 
struct SPOT  //所有点的坐标结构 
{
	int x;
	int y;
}spot[col*row]; 
struct LINE //直线结构体 存贮A,B,C 和value 
{
	int A;
	int B;
	int C;
	int value; 
}line[max];
int sum = 0;  //累计直线的数量 
int sczx(int,int,int,int); //生成两点确定的直线方程 
int gcd(int,int);
int main()
{
	int k,i,j;
	k=0;
	for(i=0;i<col;i++)  //初始化各个点坐标 
	{
		for(j=0;j<row;j++)
		{
			spot[k].x = i;
			spot[k].y = j;
			k++;
		}
	}
	for(i=0;i<col*row;i++)
	{
		for(j=i+1;j<col*row;j++)
		{	
			sczx(spot[i].x,spot[i].y,spot[j].x,spot[j].y);
		}
	}
	for(i=1; i<sum; i++)         //去重方法实现 
	{
		for(j=0; j<i; j++)
		{
			if( line[i].A == line[j].A && line[i].B == line[j].B && line[i].C == line[j].C )
			{
				line[i].value = line[i-1].value;
				break;
			} 
			line[i].value = line[i-1].value + 1;
		}
	} 
	/*for(i=0; i<sum; i++)   //检测代码1  
	//{
	//	printf("第%d条直线的参数：A=%d ，B=%d ， C=%d ， value=%d \n",i,line[i].A,line[i].B,line[i].C,line[i].value);
	//}
	*/
	printf("%d",line[sum-1].value + col + row);
	return 0;
} 
int sczx(int x1,int y1,int x2,int y2){  //计算出(x1,y1)(x2,y2)两点确定的直线方程。 
	int A,B,C; 
	if(x1 == x2){ return 0; }
	if(y1 == y2){ return 0; }
	if(x1 != x2 && y1 !=y2){ A = y1-y2; B = x2-x1; C = x1*y2 - y1*x2;	}
	int fm; 
	if(C == 0){ fm = gcd(A,B);}  //过原点，且不平行于x或y轴的直线 也需要对A和B约分处理。 
	else{fm = gcd(gcd(A,B),C);}
	line[sum].A = A/fm;
	line[sum].B = B/fm;
	line[sum].C = C/fm;
	line[sum].value = 1;
	//printf("%dx + %dy + %d = 0  过点(%d,%d)(%d,%d) \n",line[sum].A,line[sum].B,line[sum].C,x1,y1,x2,y2); //检测代码2 
	sum++;
	return 0;
}
int gcd(int m,int n){    //寻找出m,两个数值绝对值的最大公约数。 
	if(m == 0 || n == 0) return 1;
	if(m<0){ m = 0 - m; }
	if(n<0){ n = 0 - n; }
	if(m < n){
		m = n - m;
		n = n - m;
		m = n + m; 
	}
	int r = m % n;
	while(r != 0)
	{
		m = n;
		n = r;
		r = m%n;
	}
	return n;
}