149. Max Points on a Line

Given npoints on a 2D plane, find the maximum number of points that lie on the same straight line.

S: hash map + math O(logn*n^2)

三点在一条直线上的条件是任意两点组成的直线斜率相等，即k = (y1-y2)/(x1-x2)=(y1-y3)/(x1-x3). 对Δy/Δx = k，将Δy,Δx分别除以其最大公约数得到的pair(x, y)作为key，用hash map存储每个key出现的次数 （unordered_map不支持pair做key，用map代替).

这里用pair而不是用斜率k本身做key是为了避免小数点不准确。

/**
 * Definition for a point.
 * struct Point {
 *     int x;
 *     int y;
 *     Point() : x(0), y(0) {}
 *     Point(int a, int b) : x(a), y(b) {}
 * };
 */
class Solution {
public:
    int maxPoints(vector<Point>& points) {
        if (points.size() == 0) return 0;
        int maxNum = 1;
        for (int i = 0; i < points.size(); ++i) {
            map<pair<int, int>, int> count;
            int samePoint = 1, verticalPoint = 0;
            for (int j = i + 1; j < points.size(); ++j) {
                if (points[i].x == points[j].x) {
                    if (points[i].y != points[j].y) {
                        verticalPoint++;
                    } else {
                        samePoint++;
                    }
                } else {
                    int y = (points[i].y - points[j].y); 
                    int x = (points[i].x - points[j].x);
                    int gcdxy = gcd(x, y);  //greatest common divisor
                    if (gcdxy != 0) {
                        x /= gcdxy;
                        y /= gcdxy;
                    }
                    count[make_pair(x, y)]++;
                }
            }
            int localMax = verticalPoint;
            for (const auto& record : count) {
                localMax = max(localMax, record.second);
            }
            localMax += samePoint;
            maxNum = max(localMax, maxNum);
        }
        return maxNum;
    }
    int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }
};

356. Line Reflection

Given n points on a 2D plane, find if there is such a line parallel to y-axis that reflect the given points.

Example 1:

Givenpoints=[[1,1],[-1,1]], returntrue.

Example 2:

Givenpoints=[[1,1],[-1,-1]], returnfalse.

S: hashtable + math O(n)

对称轴是(maxx + minx) / 2, 已知对成轴后查找每个点的对称点是否存在， 假设x1, x2对称，则 x1 + x2 = minx + miny

    bool isReflected(vector<pair<int, int>>& points) {
        if (points.size() == 0) return true;
        unordered_map<int, unordered_set<int>> xToy;
        int maxx = INT_MIN, minx = INT_MAX;
        for (auto p : points) {
            xToy[p.second].insert(p.first);
            maxx = max(maxx, p.first);
            minx = min(minx, p.first);
        }

        int sum = maxx + minx;
        for (auto i : xToy) {
            for (int x : i.second) {
                if (i.second.find(sum - x) == i.second.end()) return false;
            }
        }
        return true;
    }