Advertisement
goshansmails

Untitled

Mar 16th, 2020
83
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.57 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <unordered_map>
  4. #include <unordered_set>
  5.  
  6. using namespace std;
  7.  
  8. struct Point{
  9.     int x, y;
  10. };
  11.  
  12. // duplicate points have weight
  13. /*
  14. bool HasVerticalSymLine(int n, const Point p[]) {
  15.     if (n == 0) {
  16.         return true;
  17.     }
  18.     int sum_of_x = 0;
  19.     for (int i = 0; i < n; i++) {
  20.         sum_of_x += p[i].x * 2;
  21.     }
  22.     if (sum_of_x % n != 0) {
  23.         return false;
  24.     }
  25.  
  26.     int possible_axis = sum_of_x / n;
  27.     unordered_map<int, unordered_map<int, int>> y_to_x_with_weight;
  28.     for (int i = 0; i < n; ++i) {
  29.         y_to_x_with_weight[p[i].y][p[i].x * 2 - possible_axis]++;
  30.     }
  31.     for (auto& [y, m_x_counter] : y_to_x_with_weight) {
  32.         for (auto& [x, counter] : m_x_counter) {
  33.             if (m_x_counter.count(-x) > 0 && m_x_counter[x] == m_x_counter[-x])
  34.             {
  35.                 continue;
  36.             }
  37.             return false;
  38.         }
  39.     }
  40.     return true;
  41. }
  42. */
  43.  
  44. // repeated points do not affect the result
  45. bool HasVerticalSymLine(int n, const Point p[]) {
  46.     if (n == 0) {
  47.         return true;
  48.     }
  49.  
  50.     int x_min = p[0].x;
  51.     int x_max = p[0].x;
  52.     for (int i = 1; i < n; i++) {
  53.         x_max = max(x_max, p[i].x);
  54.         x_min = min(x_min, p[i].x);
  55.     }
  56.  
  57.     int possible_axis = x_max + x_min;
  58.     unordered_map<int, unordered_set<int>> y_to_x;
  59.     for (int i = 0; i < n; ++i) {
  60.         y_to_x[p[i].y].insert(2 * p[i].x - possible_axis);
  61.     }
  62.     for (const auto& item : y_to_x) {
  63.         for (int x : item.second) {
  64.             if (item.second.count(-x) == 0) {
  65.                 return false;
  66.             }
  67.         }
  68.     }
  69.     return true;
  70. }
  71.  
  72.  
  73. int main() {
  74.  
  75.     {
  76.         int n = 3;
  77.         Point p[] = {
  78.                 {0, 0},
  79.                 {1, 1},
  80.                 {-1, 1}
  81.         };
  82.         if (HasVerticalSymLine(n, p)) {
  83.             cout << "YES" << endl;
  84.         } else {
  85.             cout << "NO" << endl;
  86.         }
  87.     }
  88.  
  89.     {
  90.         int n = 4;
  91.         Point p[] = {
  92.                 {1, 1},
  93.                 {2, 2},
  94.                 {1, 2},
  95.                 {2, 3}
  96.         };
  97.         if (HasVerticalSymLine(n, p)) {
  98.             cout << "YES" << endl;
  99.         } else {
  100.             cout << "NO" << endl;
  101.         }
  102.     }
  103.  
  104.     {
  105.         int n = 3;
  106.         Point p[] = {
  107.                 {0, 0},
  108.                 {0, 99},
  109.                 {0, 1}
  110.         };
  111.         if (HasVerticalSymLine(n, p)) {
  112.             cout << "YES" << endl;
  113.         } else {
  114.             cout << "NO" << endl;
  115.         }
  116.     }
  117.  
  118.     {
  119.         int n = 3;
  120.         Point p[] = {
  121.                 {0, 0},
  122.                 {0, 0},
  123.                 {1, 0}
  124.         };
  125.         if (HasVerticalSymLine(n, p)) {
  126.             cout << "YES" << endl;
  127.         } else {
  128.             cout << "NO" << endl;
  129.         }
  130.     }
  131.  
  132.     {
  133.         int n = 6;
  134.         Point p[] = {
  135.                 {2, 0},
  136.                 {2, 0},
  137.                 {3, 0},
  138.                 {3, 0},
  139.                 {1, 2},
  140.                 {4, 2}
  141.         };
  142.         if (HasVerticalSymLine(n, p)) {
  143.             cout << "YES" << endl;
  144.         } else {
  145.             cout << "NO" << endl;
  146.         }
  147.     }
  148.  
  149.     {
  150.         int n = 7;
  151.         Point p[] = {
  152.                 {2, 0},
  153.                 {2, 0},
  154.                 {3, 0},
  155.                 {3, 0},
  156.                 {1, 2},
  157.                 {4, 2},
  158.                 {4, 2}
  159.         };
  160.         if (HasVerticalSymLine(n, p)) {
  161.             cout << "YES" << endl;
  162.         } else {
  163.             cout << "NO" << endl;
  164.         }
  165.     }
  166.     return 0;
  167. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement