# 7-line C++ concise solution, NO double hash key or GCD for slope

• The key to this problem is how to characterize "slope" determined by two points. I see many posts here using either a `double`to represent slope or `pair<int,int>`with GCD process to make it unique. But this either has issues with numerical accuracy or having to do the recursive calculation.

The idea here is to simply define an order of slope in the representation of `pair<int,int>`:

Define slope `a:=(a.x, a.y)`is less than slope `b:=(b.x, b.y)` if

• `(a.y*b.y > 0)? a.x*b.y < a.y*b.x : a.x*b.y > a.y*b.x`.

Note that this formulation is actually an extension to the traditional slope calculation `x/y` which not only needs to deal with `y == 0`as corner case but also unavoidably involves floating point numerical comparison.

Once the order is defined, it can be used as a key in `std::map` for counting purpose to gather points along the same line with a reference point, i.e.,

• define `map<Point, int> count` with `count[Point(x,y)]` being the number of points with slope `(x,y)` to the reference point.

Note that we count singular slope `(0,0)` (i.e., duplicated points) separately since this "special" slope is essentially undefined.

Since an ordered container `std::map`is used, the time complexity is `O(N^2*logN)`. The space complexity is `O(N)`to store `map<Point, int> count`.

``````    int maxPoints(vector<Point>& pts) {
int maxPts = 0;
for (auto& i:pts) {
map<Point, int, Comp> count; int dup = 0;
for (auto& j:pts) {
int curMax = (i.x==j.x && i.y==j.y)? ++dup : ++count[Point(i.x-j.x,i.y-j.y)]+dup;
maxPts = max(maxPts, curMax);
}
}
return maxPts;
}

struct Comp { // comparator for key (slope) in map
bool operator()(const Point& a, const Point& b)
{
int64_t diff = (int64_t)a.x*b.y - (int64_t)a.y*b.x; // convert to 64bit int for int overflow
return (int64_t)a.y*b.y>0? diff > 0 : diff < 0;
}
};
``````

• You still have a bug, though, due to overflow. For example you fail input `[[0,0],[65536,65536],[65536,131072]]`, returning 3 instead of the correct 2. (And the judge solution fails it as well, expecting 3.) (got fixed)

• [[0,0],[65536,65536],[65536,131072]]

Yeah, you are right. For variable range in `|x| <= MAX`, expression `f = x1*x2-x3*x4` should be able to handle range `|f| <= 2*MAX^2`. By definition of struct `Point`, I modified `Comp` to convert to `int64_t` to handle `int` overflow.

Thanks for the test case `[[0,0],[65536,65536],[65536,131072]]` which should have been added to OJ's tests with expected result `2` (instead of `3`).

• @zzg_zzm Thanks, just added @StefanPochmann 's test case.

• Does it work if count[XXX] gets increased first and then dup gets increased? Say count 0 => 10 then dup 0 => 10, maxPts should be 20 instead of 10.

• Does it work if count[XXX] gets increased first and then dup gets increased? Say count 0 => 10 then dup 0 => 10, maxPts should be 20 instead of 10.

I get your point. Yes, if the "anchor" point is duplicated with last point in vector `pts`, we indeed miss some counting. However, this does not matter because we are looping through all points anyway. If not all points are duplicated, we must at some point use an "anchor" point which is not duplicated with `pts[N-1]` and this will get correct max count at least once, so we can simply update global max count by a single line `maxPts = max(maxPts, i.x==j.x && i.y==j.y? ++dup : (++count[Point(i.x-j.x,i.y-j.y)]+dup))` inside double loops.

Well, I admit that it is not readable...The readable one should count `dup` and max value in map `count[]` before updating global max count.

``````    int maxPoints(vector<Point>& pts) {
int maxPts = 0;
for (auto& i:pts) {
map<Point, int, Comp> count; int dup = 0, maxCount = 0;
for (auto& j:pts) {
if (i.x==j.x && i.y==j.y)
++dup;
else
maxCount = max(maxCount, ++count[Point(i.x-j.x,i.y-j.y)]);
}
maxPts = max(maxPts, maxCount + dup);
}
return maxPts;
}
``````

• That is even more clever than the GCD in my opinion. Nice.

Does the map type have an O(n) lookup or O(1) lookup? Curios? Just wondering where the logN came from?

• @dingess `std::map` in C++ STL library is map sorted by keys, so its lookup time is `O(logN)`.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.