Max Points on a Line
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
- 题目大意：给定n个二维平面上的点，求出这n个点当中最多有多少个点在同一直线上。
- 解题思路：每次取定一个点p1，然后求出p1与其他的n-1个点的斜率，并统计斜率相同的数目，取最大值即可。
- 具体实现：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
|
#include <iostream>
#include <map>
#include <climits>
using
namespace
std;
struct
Point {
int
x;
int
y;
Point() : x(0), y(0) {}
Point(
int
a,
int
b) : x(a), y(b) {}
};
class
Solution {
public
:
int
maxPoints(vector<Point> &points) {
int
maxNum =0;
int
size = points.size();
int
i,j;
if
(size <=2)
//如果点的个数小于3个，则最大数目为点的个数
return
size;
for
(i=0;i<size;i++)
{
int
cnt =0;
map<
double
,
int
> mp;
for
(j=0;j<size;j++)
{
if
(i==j)
continue
;
if
(points[i].x == points[j].x && points[i].y == points[j].y)
{
cnt++;
continue
;
}
//注意当直线与y轴平行的情况
double
slope = points[i].x == points[j].x ? INT_MAX : (
double
)(points[j].y - points[i].y)/(points[j].x - points[i].x);
mp[slope]++;
}
if
(mp.size()==0)
//防止mp为空时，下面的for循环不执行
mp[INT_MIN] =0;
map<
double
,
int
>::iterator it = mp.begin();
for
(;it!=mp.end();it++)
{
if
(it->second+ cnt > maxNum)
maxNum = it->second +cnt;
}
}
return
maxNum+1;
}
};
int
main(
int
argc,
char
*argv[])
{
vector<Point> points;
Point point[3];
int
i=0;
for
(i=0;i<3;i++)
{
point[i].x = 1;
point[i].y= 1;
points.push_back(point[i]);
}
Solution solution;
cout<<solution.maxPoints(points);
return
0;
}
|
这里要注意3个地方：
1）如果点的个数小于3个，则最大数目为点的个数；
2）考虑重复点的情况，重复点是无法计算斜率的；
3）考虑直线与y轴平行时，斜率为无穷大的情况。
本文转载自海 子博客园博客，原文链接：http://www.cnblogs.com/dolphin0520/p/3737561.html如需转载自行联系原作者
