首页 > 代码库 > UVa: 1595 - Symmetry
UVa: 1595 - Symmetry
题目链接:http://http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4470
题目描述:给出平面上N(N<=1000)个点。问是否可以找到一条竖线,使得所有点左右对称,如图所示:
则左边的图形有对称轴,右边没有。
思路:如点集存在对称轴,则对称轴为点集x坐标和的平均。然后用set存储每个点(输入点不同),遍历每一个点,通过求得的对称轴,计算它的对称点,若不存在则输出“NO”。
代码如下:
#include <iostream> #include <string> #include <vector> #include <set> #include <map> #include <sstream> #include <fstream> using namespace std; #define FILE typedef pair<int,int> point; int main(int argc, char* argv[]) { #ifdef FILE ifstream in("data.txt"); ofstream out("output.txt"); cin.rdbuf(in.rdbuf()); cout.rdbuf(out.rdbuf()); #endif int T; cin>>T; for(int i=0;i<T;i++) { int n; set<point> data; cin>>n; int sum = 0; for(int j=0;j<n;j++) { int x,y; cin>>x>>y; sum+=x; data.insert(point(x*n,y)); } bool flag = true; for(set<point>::iterator i=data.begin();i!=data.end();i++) { point p = *i; if(data.find(point(2*sum-p.first,p.second))==data.end()) { flag = false; break; } } if(flag==true) { cout<<"YES"<<endl; } else { cout<<"NO"<<endl; } } return 0; }
UVa: 1595 - Symmetry
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。