轴对称

题目描述

给定平面上的n个点，问是否存在一条平行于y轴的直线，使得这n个点相对于这条直线对称。

Follow-up

是否存在一条直线使得这n个点关于这条直线对称？

算法分析

因为对称轴一定平行于y轴，对称轴的特点就是每一个点都在另一边有一个对应的点。最左边的点一定对应某个最右边的点，因此最左边的点和最右边的点的中点应该在对称轴上。

找到了对称轴的位置，我们就可以通过HashMap判断是否每一个点都有对应的点，最后输出答案即可。

时间复杂度为O(n)。

参考程序

#include 
#include 
#include 
#include 
#include using namespace std;const int INF = 1<<30;struct Point {int x;int y;Point(int x=0, int y=0) : x(x), y(y) {}
};vector points;
map<int, set<int> > pmap;int main()
{int n;while (cin >> n) {Point p;for (int i=0; icin >> p.x >> p.y;points.push_back(p);}int maxv = -INF, minv = INF;for (int i=0; ibool flag = true;for (int i=0; iset<int> &setx = pmap[points[i].y];if (setx.find(maxv + minv - points[i].x) == setx.end()) {flag = false;break;}}flag ? cout << "YES\n" : cout << "NO\n";points.clear();pmap.clear();}return 0;
}

LeetCode相关练习题

https://leetcode.com/problems/max-points-on-a-line/

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！