题目描述
平面上有n个点,现在你需要建造两条路，一条是斜率为1,
另一条斜率为-1
你的任务是让这两条路经过尽可能多的点
求最多经过几个点
输入描述:
第一行输入一个整数n
第二行输入n个整数表示x坐标
第三行输入n个整数表示y坐标
数据保证没有重点
1 ≤ N ≤ 1000,0 ≤ x[i],y[i] ≤ 999
输出描述:
输出一个整数
示例1
输入
4 1 4 4 5 3 0 2 3
输出
4
示例2
6 0 1 2 3 4 5 2 2 2 2 2 2
输出
2
示例3
输入
4 2 2 3 3 2 3 2 3
输出
4
思路:
直线可以表示为 y = x + b,对于斜率固定,我们可以用b来指代直线.
对于同一条斜率为1的直线 , y-x 的值相同.对于同一条斜率为-1的直线,y+x的值相同.
所以我们可以先用两个数组存入这n个点,然后统计所有的 直线 以及 经过的点数.分别存入两个map集合中.
最后每次选取两条直线,统计其经过的点的总数.每求一次就要更新下结果.
参考代码
#include<bits/stdc++.h> using namespace std; const int maxn = 1000+10; int X[maxn],Y[maxn],n,ans; map<int,int> m1,m2;//存放所有直线以及其经过的点数. m1:+1 m2:-1 int solve(int b1,int b2) {//求 两条直线经过的点总数. int total = 0; for(int i = 1; i <=n ; i++) { if((Y[i]-X[i] == b1)||(Y[i]+X[i]==b2)) { total++; } } return total; } int main() { cin>>n; for(int i = 1; i <= n; i++) { cin>>X[i]; } for(int j = 1; j <= n; j++) { cin>>Y[j]; } for(int i = 1; i <= n; i++) { m1[Y[i]-X[i]]++;// 存入斜率为1所有的直线 以及经过的点数 每条直线用b来代替 m2[Y[i]+X[i]]++;// 存入斜率为-1所有的直线 以及经过的点数 } for(map<int,int>::iterator it = m1.begin(); it!=m1.end(); it++) {//任取两条直线进行枚举. for(map<int,int>::iterator it2 = m2.begin(); it2 != m2.end(); it2++) { ans = max(ans,solve(it->first,it2->first));//每次更新ans. } } cout<<ans<<endl; return 0; }
