题意
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
意思就是说在给定的节点中计算出在同一条直线上的最大节点个数。
思路
这道题，题意很容易理解，但是需要注意的东西包括，如果你用斜率计算，那么就需要注意到精确度的问题，否则就会变成相等的斜率，无奈之下，只能提高精确度，比如说用long double，但这不是持久的办法，目前的办法是使用最大公约数。
其实我大概的思路已经想到了，就是第五种方法的思路，这道题没做出来的原因是，没有考虑到相同点以及相同的x的情况。
代码
#include <stdio.h>
#include <stdio.h>
#include <string>
#include <vector>
#include <iostream>
#include <unordered_map>
#include <map>
#include <set>
using namespace std;
/**
* Definition for a point.
*/
struct Point {
int x;
int y;
Point() : x(0), y(0) {}
Point(int a, int b) : x(a), y(b) {}
};
/**
* 第一种方法：将每一个顶点和其他的顶点进行计算得出斜率，
* 用hash保存下来，key为斜率，value为总个数
* 因为相同斜率的则在同一条线上
*
* @param points <#points description#>
*
* @return <#return value description#>
*/
int maxPoints(vector<Point>& points) {
unordered_map<int, int> hash;
int maxCnt = 0;
auto caculateK = [&](Point p1, Point p2) {
int k = (p2.y - p1.y)/(p2.x - p1.x);
return k;
};
for (int i = 0; i < points.size(); i++) {
Point pointA = points[i];
for (int j = 0; j < points.size() && i != j; j++) {
Point pointB = points[j];
int k = caculateK(pointA, pointB);
if (hash.find(k) != hash.end()) {
hash[k]++;
}
else {
hash.insert(make_pair(k, 1));
}
}
// hash.clear();
}
for (auto itr = hash.begin(); itr != hash.end(); itr++) {
maxCnt = std::max((*itr).second, maxCnt);
}
return maxCnt + 2;
}
/**
* 计算最大公约数
*/
int GCD(int a, int b) {
if(b==0) return a;
else return GCD(b, a%b);
}
/**
* 这个方法不再是使用斜率作为map的key，而是使用的是gcd(最大公约数)
* 总之结果就是overlap＋localmax＋vertical＋1，
* 其中overlap代表的是完全相同的顶点，vertical代表的是只有x是相等的，因为相减会导致0
*
* @param points <#points description#>
*
* @return <#return value description#>
*/
int maxPoints2(vector<Point>& points) {
if (points.size() < 2) {
return (int)points.size();
}
int result = 0;
for (int i = 0; i < points.size(); i++) {
map<pair<int, int>, int> lines;
int localmax = 0, overlap = 0, vertical = 0;
for (int j = i+1; j < points.size(); j++) {
// 相同的点的个数
if (points[j].x == points[i].x && points[j].y == points[i].y) {
overlap++;
continue;
}
else if (points[j].x == points[i].x) {
vertical++;
}
else {
int a=points[j].x-points[i].x, b=points[j].y-points[i].y;
int gcd=GCD(a, b);
a/=gcd;
b/=gcd;
lines[make_pair(a, b)]++;
localmax=std::max(lines[make_pair(a, b)], localmax);
}
localmax=std::max(vertical, localmax);
}
// 结果为
result = std::max(result, localmax+overlap+1); //这里加一是因为之前vertical只计算了一次
}
return result;
}
// 由于精确度问题，更改double
inline bool double_equal(double a, double b) { return abs(a-b) < 1e-10; }
inline bool double_less (double a, double b) { return a-b < -1e-10; }
struct Line {
double r; // ratio ; slope
double t; // translation
Line(Point p, Point q) { // math
if (q.x == p.x) r = 1e20, t = p.x;
else
{
r = (double) (q.y-p.y) / (double) (q.x-p.x);
t = p.y - p.x * r;
}
}
};
// 用作排序
bool operator < (const Line& a, const Line& b) {
return a.r == b.r ? a.t < b.t : a.r < b.r;
}
// 依此来判断map中是否相等
bool operator == (const Line& a, const Line& b) {
return a.r == b.r && a.t == b.t;
}
/**
* 这个思路最大的特点就是利用了一个结构体和set的原理
* 因为set可以自动去除掉重复的元素
*
* @param points <#points description#>
*
* @return <#return value description#>
*/
int maxPoints4(vector<Point> &points) {
if (points.empty()) return 0;
map<Line, set<Point*> > line_map;
for (auto & a : points)
for (auto & b : points)
{
Line line(a,b);
line_map[line].insert(&a);
line_map[line].insert(&b);
}
int ret = 1;
for (auto & pr : line_map) ret = max(ret,(int)pr.second.size());
return ret;
}
/**
* 最直接最简单的做法
*
* @param points <#points description#>
*
* @return <#return value description#>
*/
int maxPoints5(vector<Point>& points) {
if(points.empty())
return 0;
else if(points.size() == 1)
return 1;
int ret = 0;
for(int i = 0; i < points.size(); i ++)
{//start point
int curmax = 1; //points[i] itself
unordered_map<long double, int> kcnt; // slope_k count
int vcnt = 0; // vertical count
int dup = 0; // duplicate added to curmax
for(int j = 0; j < points.size(); j ++)
{
if(j != i)
{
long double deltax = points[i].x - points[j].x;
long double deltay = points[i].y - points[j].y;
if(deltax == 0 && deltay == 0) {
dup ++;
}
else if(deltax == 0)
{
if(vcnt == 0)
vcnt = 2;
else
vcnt ++;
curmax = max(curmax, vcnt);
}
else
{
long double k = deltay / deltax;
if(kcnt[k] == 0)
kcnt[k] = 2;
else
kcnt[k] ++;
curmax = max(curmax, kcnt[k]);
}
}
}
ret = max(ret, curmax + dup);
}
return ret;
}
int main(int argc, const char * argv[]) {
vector<Point> points;
Point point1(0, 0), point2(94911151, 94911150), point3(94911152, 94911151), point4(5, 6);
points.push_back(point1);
points.push_back(point2);
points.push_back(point3);
int result = maxPoints5(points);
cout << "result..." << result << endl;
return 0;
}