356. Line Reflection (Medium)

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:

Given points = [[1,1],[-1,1]], return true.

Example 2:

Given points = [[1,1],[-1,-1]], return false.

Follow up:

Could you do better than $$O(n^2)$$?

Hint:

1. Find the smallest and largest x-value for all points.
2. If there is a line then it should be at y = (minX + maxX) / 2.
3. For each point, make sure that it has a reflected point in the opposite side.

Solution: Hint 25ms

这道题给了我们一堆点，问我们存不存在一条平行于y轴的直线，使得所有的点关于该直线对称。题目中的提示给的相当充分，我们只要按照提示的步骤来做就可以解题了。首先我们找到所有点的横坐标的最大值和最小值，那么二者的平均值就是中间直线的横坐标，然后我们遍历每个点，如果都能找到直线对称的另一个点，则返回true，反之返回false，参见代码如下：

class Solution {
public:
    bool isReflected(vector<pair<int, int>>& points) {
        set<pair<int,int>> s;
        int xmin = INT_MAX, xmax = INT_MIN;
        for (auto& a: points) {
            s.insert(a);
            xmin = min(xmin, a.first);
            xmax = max(xmax, a.first);
        }

        double a = (double)(xmin+xmax)/2;
        for (auto& b: points) {
            if (s.count({2*a-b.first,b.second}) == 0) return false; 
        }
        return true;
    }
};