Line Through Points

• Time : O(n^2)
• Space : O(n)

#include <vector>
using namespace std;

string degree(int y1, int x1, int y2, int x2) {
    int Y = y1 - y2, X = x1 - x2;
		int sign = Y * X >= 0 ? 1 : -1;
		Y = abs(Y), X = abs(X);
    if(Y != 0 and X != 0) {
        int gcd = __gcd(Y, X);
        Y /= gcd; X /= gcd;
    } else if(Y == 0) return "0#1";
		else if(X == 0) return "1#0";
    return (sign == -1 ? "-" : "+") + to_string(Y) + "#" + to_string(X);
}

int lineThroughPoints(vector<vector<int>> points) {
    int n = points.size(), res = 0;
    for(int i = 0; i < n; i++) {
        unordered_map<string, int> mp;
        for(int j = i + 1; j < n; j++) {
            res = max(res, ++mp[degree(points[i][0], points[i][1], points[j][0], points[j][1])]);
        }
    }
    return res + 1;
}