Symmetry

也可以查看我的个人博客，秋梨膏，(☆ω☆)
题目链接

题意：一共T组数据，每组输入N个点，N<=1000，问这些点是否关于某个竖线对称

思路：
1、假设这些所有点中x最小为a，最大为b，那么如果这些点关于某条竖线对称，那么一定是(a+b)/2，因为最左端的点一定是和最右端的点对称的。
2、假设竖线的横坐标是x，那么可以知道x = (a + b) / 2 ,a和b的含义同1中的a和b，那么对于任何一个点(c,d)，他关于x的对称点就是 x + (x - c) ,那么联立两个式子可以知道对称点就是 (a + b - c , d) , 这样就省略了除的过程。

一开始没想到肯定是关于(a+b)/2对称的，还一个个的去枚举找中间点，太蠢了、、、、（╯‵□′）╯︵┴─┴
代码：

#include 
#include 
#include 
#include using namespace std;const int N = 1010;
typedef pair <int , int > PII;int n;
PII arr[N];bool judge(int x)
{map < PII , int > mp;for(int i = 0 ; i < n ; ++ i){int a = arr[i].first , b = arr[i].second;//c是与(a,b)关于x/2的对称点的x坐标int c = x - a;//如果这个点本身就在对称轴上if(c == a) continue;//如果有其他点的对称点是(a,b)，直接减一即可if(mp.find({a , b}) != mp.end() && mp[{a , b}] > 0) mp[{a , b}] -= 1;//如果没有其他点的对称点是(a,b)，那么(a,b)点就需要(c,b)点与它形成对称关系else if(mp.find({c , b}) == mp.end()) mp[{c , b}] = 1;else if(mp.find({c , b}) != mp.end()) mp[{c , b}] += 1;}//循环判断for(auto i : mp)if(i.second) return false;return true;
}int main(void)
{int T;cin >> T;while(T --){scanf("%d",&n);//left和right分别为最左端的x和最右端的x值int left = 10010 , right = -10010;for(int i = 0 ; i < n ; ++ i){int a , b;scanf("%d %d",&a , &b);arr[i] = {a , b} ;left = min(left , a);right = max(right , a);}if(judge(left + right)) puts("YES");else puts("NO");}return 0;
}

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