给定一个二维平面，平面上有 n 个点，求最多有多少个点在同一条直线上。
示例 1:
输入: [[1,1],[2,2],[3,3]]
输出: 3
解释:
^
|
| o
| o
| o
+------------->
0 1 2 3 4
示例 2:
输入: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输出: 4
解释:
^
|
| o
| o o
| o
| o o
+------------------->
0 1 2 3 4 5 6 看到此题，第一想法是用一个数据结构来表示某一条直线，直线的表达式有y = ax + b ,那提取出 a和b是不是就可以了，写完发现还有x = 1这种直线。然后想通过hashmap来保存直线对应的点数，如果参数a和b是个1/3这种值，由于精度问题，算出来的两个直线的数据结构的hash值就不一样，hashmap就是认为是两个key。 最后无奈换成分数表达式 y = (a1/a2)*x + b1/b2; b1/b2 = (a2*y - a1*x)/a2;这样4个int变量，就可以精确表示一条直线.当然，分数需要进行约分！
struct FPoint {
int a1;
int a2;
int b1;
int b2;
FPoint() : a1(), a2(), b1(), b2() {}
FPoint(int _a1, int _a2)
{
if (_a1 * _a2 > )
{
a1 = abs(_a1);
a2 = abs(_a2);
}
else
{
a1 = - * abs(_a1);
a2 = abs(_a2);
}
b1 = ;
b2 = ;
}
bool Contain(Point p)const
{
long long int t1 = 1L, t2 = 1L;
t1 = t1 * p.y * (a2*b2);
t2 = t2 * a1*b2*p.x + b1*a2;
return a2 == ? p.x == b1 / b2 : t1 == t2;
}
void Normal()
{
if (a1 == && a2 == )
{
}
else if (a1 == )
a2 = ;
else if (a2 == )
a1 = ;
else
{
int s = a1*a2 > ? : -;
a1 = abs(a1);
a2 = abs(a2);
int _gcd = GCD(a1, a2);
a1 = s * a1 / _gcd;
a2 = a2 / _gcd;
if (b1 == )
b2 = ;
else
{
s = b1*b2 > ? : -;
b1 = abs(b1);
b2 = abs(b2);
_gcd = GCD(b1, b2);
b1 = s * b1 / _gcd;
b2 = b2 / _gcd;
}
}
}
//最大公约数
int GCD(int a, int b){
int m = a, n = b, r;
if (m < n){
int temp = m;
m = n;
n = temp;
}
r = m % n;
while (r){
m = n;
n = r;
r = m % n;
}
return n;
}
};
struct RecordHash
{
size_t operator()(const FPoint& f) const{
return hash<int>()(f.a1) ^ hash<int>()(f.a2) ^ hash<int>()(f.b1) ^ hash<int>()(f.b2);
}
};
struct RecordCmp
{
bool operator()(const FPoint& f1, const FPoint& f2) const{
return f1.a1 == f2.a1 && f1.a2 == f2.a2 &&f1.b1 == f2.b1&&f1.b2 == f2.b2;
}
};
class Solution {
public:
FPoint GetPoint(Point a, Point b)
{
FPoint f(b.y - a.y, b.x - a.x );
if (f.a2 == )
{
f.b1 = a.x;
f.b2 = ;
}
else
{
f.b1 = (f.a2*a.y - f.a1*a.x);
f.b2 = f.a2;
}
return f;
}
int maxPoints(vector<Point>& points) {
if (points.size() <= )
{
return points.size();
}
unordered_set<int> index_set;
unordered_map<FPoint, int, RecordHash, RecordCmp> line_map;
int max_point = ;
for (int i = ; i < points.size(); i++)
{
unordered_map<FPoint, int, RecordHash, RecordCmp>::iterator itr = line_map.begin();
for (; itr != line_map.end(); itr++)
{
if (itr->first.Contain(points[i]))
{
itr->second++;
max_point = max(max_point, itr->second);
if (index_set.count(i) == )index_set.insert(i);
}
}
for (int r = ; r < points.size() ; r++)
{
if (r != i && index_set.count(r) == )
{
FPoint f = GetPoint(points[i], points[r]);
f.Normal();
if (line_map[f] == )
{
line_map[f]++;
}
if (index_set.count(i) == )
{
index_set.insert(i);
}
max_point = max(max_point, line_map[f]);
}
}
}
return max_point;
}
};
