MEGChai MEGChai
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
首页 › 数据结构与算法 › 在线评测 › UVaOJ 1595 - Symmetry
AOAPC II

UVaOJ 1595 - Symmetry

Chai
2021-11-24 0:00:00在线评测阅读 468

问题描述

p1595

原题链接:UVaOJ 1595 - Symmetry

相关说明:本题为《算法竞赛入门经典(第2版)》习题 5-6

解法一:集合

这题给的假设比较多,因此情况比较简单,可以通过求所有点横坐标的中点来找到假想的对称轴,然后进行验证。注意由于给出的点坐标都是整数,因此对称轴有可能出现小数部分出现 0.5 点的情况,因此需要用 double 来算(但也不会出现其它的值,因此在此题的情况下可以很方便求出对称点进行逐个验证,不用考虑浮点误差的处理)。

C++
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;
}
Python
1
#TODO
AOAPC II UVaOJ
赞赏 赞(0)
订阅
提醒
guest
guest
0 评论
内嵌评论
查看所有评论
  • 0
  • 0
Copyright © 2020-2023 MEGChai.
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
# 生活 # # 心理 # # 编程 # # 音乐 # # 写作 #
Chai
95
文章
4
评论
58
喜欢
wpDiscuz