# Share my solution <A,B,C> (Line Ax+By+C=0) as hash key instead of using slope(double) as hash key

• The idea is easy to understand, the general form of a line is Ax+By+C = 0, so the tuple<A,B,C> determines a line, we use this tuple as hash key, calculate the line formed by every two points, and insert the two points in the corresponding line determined by (A, B, C).

``````int GCD(int a, int b) {
if (b == 0) return a;
else return GCD(b, a%b);
}

struct cmp {
bool operator() (const Point& a, const Point& b) const  {
if (a.x != b.x) return a.x < b.x;
else return a.y < b.y;
}
};

inline vector<int> LinebyTwoPoints(Point a, Point b) {
int A = b.y - a.y;
int B = a.x - b.x;
int C = b.x * a.y - a.x * b.y;

// cout << " A = " << A;
// cout << " B = " << B;
// cout << " C = " << C << endl;

if (A != 0 && B != 0 && C != 0) {
int d = GCD(GCD(A, B), C);
A /= d; B /= d; C /= d;
} else if (A == 0 && C == 0 && B != 0) {
B = 1;
} else if (B == 0 && C == 0 && A != 0) {
A = 1;
} else if (C == 0 && A != 0 && B != 0) {
int d = GCD (A, B);
A /= d; B /= d;
} else if (A == 0 && B != 0 && C != 0) {
int d = GCD(B, C);
B /= d; C /= d;
} else if (B == 0 && A != 0 && C != 0) {
int d = GCD(A, C);
A /= d; C /= d;
}
vector<int> ans;
ans.push_back(A);
ans.push_back(B);
ans.push_back(C);
//cout << "after norm:" << endl;
// cout << "\t A = " << A;
//cout << "\t B = " << B;
//cout << "\t C = " << C << endl;
return ans;
}
int maxPoints(vector<Point>& points) {
if (points.size() <= 1) return points.size();
map<vector<int>, set<Point, cmp>> tb;
int n = (int) points.size();

map<Point, int, cmp> p_cnt;
for (int i = 0; i < n; ++i) {
p_cnt[points[i]]++;
}

for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (!(points[i].x == points[j].x && points[i].y == points[j].y)) {
vector<int> line = LinebyTwoPoints(points[i], points[j]);
tb[line].insert(points[i]);
tb[line].insert(points[j]);
}
}
}

int cnt = 0;
for (auto it = tb.begin(); it != tb.end(); ++it) {
int temp = 0;
for (auto p : it->second) {
temp += p_cnt[p];
}
cnt = max(cnt, temp);
}
//cout << "now cnt = " << cnt << endl;

for (auto it = p_cnt.begin(); it != p_cnt.end(); ++it) {
cnt = max(cnt, it->second);
}

return cnt;
}``````

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