问题描述
p1595相关说明:本题为《算法竞赛入门经典(第2版)》习题 5-6
解法一:集合
这题给的假设比较多,因此情况比较简单,可以通过求所有点横坐标的中点来找到假想的对称轴,然后进行验证。注意由于给出的点坐标都是整数,因此对称轴有可能出现小数部分出现 0.5 点的情况,因此需要用 double 来算(但也不会出现其它的值,因此在此题的情况下可以很方便求出对称点进行逐个验证,不用考虑浮点误差的处理)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
#include <bits/stdc++.h> using namespace std; int main () { int t, n, x, y; cin >> t; while (t--) { while (cin >> n && n) { set<pair<int, int>> point; double sum_x = 0; for (int i = 0; i < n; i++) { cin >> x >> y; point.insert({x, y}); sum_x += x; } double mid_x = sum_x / n; bool flag = true; // assume that we find the line for (auto& p : point) if (!point.count({2 * mid_x - p.first, p.second})) { flag = false; break; } cout << (flag ? "YES" : "NO") << endl; } } return 0; } |
1 |
#TODO |