# My O(n^2) solution in C++ with self-defined equal and hash function

• I try to avoid compare double as machine error may lead to catastrophic result.

``````#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <utility>

using namespace std;

struct Point{
int x;
int y;
Point() : x(0), y(0) {}
Point(int a, int b) : x(a), y(b) {}
};

// Equal function for Point struct
bool operator==(const Point &p1, const Point &p2){
return p1.x == p2.x && p1.y == p2.y;
}

// HashCode fuction for Point struct
struct hashPoint{
size_t operator()(const Point &point) const{
hash<int> tmp;
return tmp(point.x) ^ (tmp(point.y) << 1);
}
};

// Find the greatest common division for two integers,
// useful in building a Line struct
int gcd(int x, int y){
if (x < y) return gcd(y, x);
if (y < 0) return gcd(x, -y);
if (y == 0) return x;
return gcd(y, x%y);
}

struct Line{
// Formula: a * x + b * y = c
int a;
int b;
int c;

// Make sure that the same line in 2D space will have the same expression
Line(int _a, int _b, int _c){
a = _a; b = _b; c = _c;
if (a < 0){
a = -a; b = -b; c = -c;
}
if (a == 0){
c = c / b; b = 1; return;
}
int max = gcd(a, b);
a = a / max; b = b / max; c = c / max;
}
};

// Equal function for Line struct
bool operator==(const Line &l1, const Line &l2){
return l1.a == l2.a && l1.b == l2.b && l1.c == l2.c;
}

// Hash function for Line struct
struct hashLine{
size_t operator()(const Line &line) const{
hash<int> tmp;
return tmp(line.a) ^ (tmp(line.b) << 1) ^ (tmp(line.c) << 2);
}
};

class Solution {
public:
int maxPoints(vector<Point> &points) {

if (points.size() == 0){
return 0;
}

// hashMap to keep all points and their counts
unordered_map<Point, int, hashPoint> record;

typedef pair<unordered_set<Point, hashPoint>, int> pSet;

// hashMap to keep all lines, their component points and counts of points.
unordered_map<Line, pSet, hashLine> lineMap;
for (Point pt : points) {
if (record.find(pt) == record.end()) {
record[pt] = 1;
}else{
record[pt] ++;
}
}

if (record.size() == 1) {
return record.begin()->second;
}

// Search all possible lines
for (auto iter = record.begin(); iter != record.end(); iter ++) {
auto iter2 = iter;
for (iter2 ++; iter2 != record.end(); iter2 ++) {
int x1 = iter->first.x, x2 = iter2->first.x;
int y1 = iter->first.y, y2 = iter2->first.y;
// Build a line with two given points.
Line line(y2 - y1, x1 - x2, x2 * y1 - x1 * y2);
if (lineMap.find(line) == lineMap.end()) {
// If this is a new line.
pSet tmp;
tmp.first.insert(iter->first);
tmp.first.insert(iter2->first);
tmp.second = iter->second + iter2->second;
lineMap[line] = tmp;
}else{
// If this line already exist, check if the second point is added.
// No need to check the first point.
// It should be added because it can be scanned before as the line already exist.
if (lineMap[line].first.find(iter2->first) == lineMap[line].first.end()) {
lineMap[line].first.insert(iter2->first);
lineMap[line].second += iter2->second;
}
}
}
}

// Find the maximum, return it.
int max = 2;
for (auto iter = lineMap.begin(); iter != lineMap.end(); iter ++) {
if (max < iter->second.second) {
max = iter->second.second;
}
}

return max;
}
};``````

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