> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/math/geometry/line-reflection.md).

# Line Reflection

<https://leetcode.com/problems/line-reflection/description/>

> 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(n2)?

## Thoughts

给一堆二维点, 问里头每个点是否都关于同一个与Y轴平行的线对称. 不难想到把x最小和最大的点查出来, 如果那条线存在, 那肯定就是它俩的中点所在的竖线. 正常来说 midX = minX + (maxX - minX) / 2 = (maxX + minX) / 2, 然后对每个x算出反射点refX = 2 *mid - x. 如果这是数学题没问题, 但编程有个精度问题, midX很可能不是整数. 但我们真的需要算出midX吗? 求refX只要2* mid就好了, 也就是minX + maxX. 成功避免了精度问题.

还有个小优化就是把点都存成string形式放入HashSet, 代码更简洁.

## Code

```
class Solution {
    public boolean isReflected(int[][] points) {
        int minX = Integer.MAX_VALUE, maxX = Integer.MIN_VALUE;
        Set<String> pts = new HashSet<>();
        for (int[] point : points) {
            minX = Math.min(minX, point[0]);
            maxX = Math.max(maxX, point[0]);
            pts.add(point[0] + "," + point[1]);
        }

        int sum = minX + maxX;
        for (int[] point : points) {
            int refX = sum - point[0];
            if (pts.contains(refX + "," + point[1])) {
                continue;
            }
            return false;
        }

        return true;
    }
}
```

## Analysis

时间复杂度O(N).