|
10鱼币
题目描述
平面上有n个点,现在你需要建造两条路,一条是斜率为1,
另一条斜率为-1
你的任务是让这两条路经过尽可能多的点
求最多经过几个点
输入描述:
第一行输入一个整数N表示点的个数
第二行输入N个数表示X坐标
第三行输入N个数表示Y坐标
1<=N<=1000 ,0<=x,y<=999
输出描述:
输出一个整数
示例1
输入
4
1 4 4 5
3 0 2 3
输出
4
说明
(1,3) (4,0) (4,2) (5,3)四个点都可以被经过
贴上我的垃圾代码
- #include<stdio.h>
- int main()
- {
- int N,i,j;
- int str1[100];
- int str2[100];
- int flag;// 判断斜率是否为1和-1
- int count = 0;//计算出经过的点
-
- scanf("%d", &N);
-
- for(i = 0; i < N; i++)
- {
- scanf("%d", &str1[i]);//输入x的值
- }
-
- for(j = 0; j < N; j++)
- {
- scanf("%d", &str2[j]);//输入y的值
- }
-
- for(i = 0; i < N; i++)
- {
- for(j = 0; j < N; j++)
- {
- flag = (str1[i+j] - str1[i])/(str2[i+j] - str2[i]);//算斜率
- while(flag == 1 || flag == -1)
- {
- count+=2;
- }
- }
- }
- printf("%d", count);
-
- }
复制代码
代码我肯定写的有问题 但本人太菜太菜 不会写这个题目
本帖最后由 前路 于 2019-2-20 00:42 编辑
以下回复为个人拙见:(诚心接受指正,不接受撕逼)
解题思路为:
利用暴力枚举列出是符合斜率的所有直线;
然后再在每条直线中枚举出所有的点;
最后进行判断输出;
知识和注意点:
1,直线公式:y=x+b;
2,x,y>0;
3,x,b都在变化,b变化时代表直线改变,x变化是代表直线上的点的变化
过程:
1,对输入格式进行分析,调试;
2,采用二维数组将测试点凸显出来用于后面的点的判断;
3,用循环for (i = 0; i < 100; i++){去枚举区域内所有符合斜率的直线
4,用循环 for (temp_x = 0; temp_x < i+1; temp_x++)去枚举每条直线的所有点
5,判断该条直线是否存在测试点
6,由于需要记录测试点存在于每条直线的情况,所以用result数组来记录每条直线上存在测试点的个数
7,遍历result数组,找出最多测试点的直线,用变量Slope_Result_1和Slope_Result_1记录最大值
8,计算总和输出结果
总结:
刚开始我的思路与楼主思路相同,但是后面发现这种思路是判断所有符合斜率的点,并不是判断所有符合斜率的同一直线上的点;
|
-
最佳答案
查看完整内容
以下回复为个人拙见:(诚心接受指正,不接受撕逼)
解题思路为:
利用暴力枚举列出是符合斜率的所有直线;
然后再在每条直线中枚举出所有的点;
最后进行判断输出;
知识和注意点:
1,直线公式:y=x+b;
2,x,y>0;
3,x,b都在变化,b变化时代表直线改变,x变化是代表直线上的点的变化
过程:
1,对输入格式进行分析,调试;
2,采用二维数组将测试点凸显出来用于后面的点的判断;
3,用循环for (i = 0; i < 100; i+ ...
|