Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <unordered_map>
- #include <unordered_set>
- using namespace std;
- struct Point{
- int x, y;
- };
- // duplicate points have weight
- /*
- bool HasVerticalSymLine(int n, const Point p[]) {
- if (n == 0) {
- return true;
- }
- int sum_of_x = 0;
- for (int i = 0; i < n; i++) {
- sum_of_x += p[i].x * 2;
- }
- if (sum_of_x % n != 0) {
- return false;
- }
- int possible_axis = sum_of_x / n;
- unordered_map<int, unordered_map<int, int>> y_to_x_with_weight;
- for (int i = 0; i < n; ++i) {
- y_to_x_with_weight[p[i].y][p[i].x * 2 - possible_axis]++;
- }
- for (auto& [y, m_x_counter] : y_to_x_with_weight) {
- for (auto& [x, counter] : m_x_counter) {
- if (m_x_counter.count(-x) > 0 && m_x_counter[x] == m_x_counter[-x])
- {
- continue;
- }
- return false;
- }
- }
- return true;
- }
- */
- // repeated points do not affect the result
- bool HasVerticalSymLine(int n, const Point p[]) {
- if (n == 0) {
- return true;
- }
- int x_min = p[0].x;
- int x_max = p[0].x;
- for (int i = 1; i < n; i++) {
- x_max = max(x_max, p[i].x);
- x_min = min(x_min, p[i].x);
- }
- int possible_axis = x_max + x_min;
- unordered_map<int, unordered_set<int>> y_to_x;
- for (int i = 0; i < n; ++i) {
- y_to_x[p[i].y].insert(2 * p[i].x - possible_axis);
- }
- for (const auto& item : y_to_x) {
- for (int x : item.second) {
- if (item.second.count(-x) == 0) {
- return false;
- }
- }
- }
- return true;
- }
- int main() {
- {
- int n = 3;
- Point p[] = {
- {0, 0},
- {1, 1},
- {-1, 1}
- };
- if (HasVerticalSymLine(n, p)) {
- cout << "YES" << endl;
- } else {
- cout << "NO" << endl;
- }
- }
- {
- int n = 4;
- Point p[] = {
- {1, 1},
- {2, 2},
- {1, 2},
- {2, 3}
- };
- if (HasVerticalSymLine(n, p)) {
- cout << "YES" << endl;
- } else {
- cout << "NO" << endl;
- }
- }
- {
- int n = 3;
- Point p[] = {
- {0, 0},
- {0, 99},
- {0, 1}
- };
- if (HasVerticalSymLine(n, p)) {
- cout << "YES" << endl;
- } else {
- cout << "NO" << endl;
- }
- }
- {
- int n = 3;
- Point p[] = {
- {0, 0},
- {0, 0},
- {1, 0}
- };
- if (HasVerticalSymLine(n, p)) {
- cout << "YES" << endl;
- } else {
- cout << "NO" << endl;
- }
- }
- {
- int n = 6;
- Point p[] = {
- {2, 0},
- {2, 0},
- {3, 0},
- {3, 0},
- {1, 2},
- {4, 2}
- };
- if (HasVerticalSymLine(n, p)) {
- cout << "YES" << endl;
- } else {
- cout << "NO" << endl;
- }
- }
- {
- int n = 7;
- Point p[] = {
- {2, 0},
- {2, 0},
- {3, 0},
- {3, 0},
- {1, 2},
- {4, 2},
- {4, 2}
- };
- if (HasVerticalSymLine(n, p)) {
- cout << "YES" << endl;
- } else {
- cout << "NO" << endl;
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement