1196: 数星星（二）（结构体专题）

题目描述

一天，小明坐在院子里数星星，Gardon就出了个难题给他，让他数数天上的星星最多有多少个是在同一条直线上的。天上的星星太多了，小明马上就看花了眼，你能写个程序来帮他计算么？

输入

首先输入一个整数N(N<=300)，接下来的N对数每对表示一个星星的位置（星星的坐标在-10000到10000之间，精确到小数点后1位）。没有两个星星会在同一个位置。

输出

一个整数，表示一条直线上最多星星的数目。

样例输入 Copy

5
0 0
1 0
1 1
0 1
0.5 0.5

样例输出 Copy

3

问题分析

星星个数已知，给所有星星一个编号从0—n-1 ，假设所有星星都不在其他星星的连线上这是最多有几条线呢，以0号星星为中心可以与1号2号......n-1号形成n-1条线，以1号星星为中心可以与2号三号......n-1号（注，以一号为中心时已经与二号形成一条线了)形成n-2条线以此类推，可得300颗星星最多形成45000条线，我们定义一个这么长的数组来储存每一条线上的星星数量，以任意两颗星星为中心看看其他星星是否在这条线上如果在则让星星数目加一，在判断星星是否在两颗星的连线上看看这一颗星与其中一颗星连线的斜率是否等于那两颗星连线的斜率即可。

代码实现

#include
struct point{
	double x;
	double y;
};
int main(){
	int n;
	int x[45000]={0};
	scanf("%d",&n);
	struct point s[300];
	for(int i=0;i
		scanf("%lf %lf",&s[i].x,&s[i].y);
	}
	int m=0;
	int max=0;
	for(int i=0;i-1;i++){
		for(int j=i+1;j
			for(int k=0;k
				if(k!=i&&k!=j&&(s[i].y-s[j].y)/(s[i].x-s[j].x)==(s[i].y-s[k].y)/(s[i].x-s[k].x)){
					x[m]++;
				}
			}
			x[m]+=2;
			if(max
				max=x[m];
			}
			m++;
		}
	}
	printf("%d",max);
	return 0;
}

提交结果