数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++中直线上的最大点数
假设我们有一个二维平面。我们必须找到位于同一条直线上的最大点数。如果点是这样的：
那么就有4个点
为了解决这个问题，我们将遵循以下步骤：
n := 点的数量，如果 n < 3，则返回 n
ans := 2
对于 i 从 1 到 n – 1 的范围
count := 0
从索引 i 和 i – 1 获取两个点，这些是 p1、p2
如果 p1 和 p2 点相同，则
对于 j 从 0 到 n – 1 的范围
如果 points[j].x = p1.x 并且 points[j].y = p1.y，则将 count 加 1
否则：
对于 j 从 0 到 n – 1 的范围
p3 := 来自索引 j 的点
如果 p3.y – p2.y * p2.x – p1.x = p2.y – p1.y * p3.x – p2.x，则将 count 加 1
ans := ans 和 count 的最大值
返回 ans
示例
让我们看看下面的实现，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
int maxPoints(vector<vector<int>>& points) {
int n = points.size();
if(n<3)return n;
int ans = 2;
for(int i = 1;i<n;i++){
int count = 0;
lli x1 = points[i-1][0];
lli x2 = points[i][0];
lli y1 = points[i-1][1];
lli y2 = points[i][1];
if(x1 == x2 && y1 == y2){
for(int j =0;j<n;j++){
if(points[j][0] ==x1 && points[j][1] == y1)count++;
}
} else {
for(int j =0;j<n;j++){
int x3 = points[j][0];
int y3 = points[j][1];
if((y3-y2)*(x2-x1) == (y2-y1)*(x3-x2))count++ ;
}
}
ans = max(ans, count);
}
return ans;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{1,1},{3,2},{5,3},{4,1},{2,3},{1,4}};
cout << (ob.maxPoints(v));
}输入
[{1,1},{3,2},{5,3},{4,1},{2,3},{1,5}]输出
4
更新于：2020年5月26日
478 次浏览
广告