The_Law

Untitled

Dec 26th, 2018
386
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.14 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. #include <string>
  5. #include <algorithm>
  6.  
  7. using namespace std;
  8.  
  9. struct Point // структура точки
  10. {
  11.     string name;
  12.     int x;
  13.     int y;
  14. };
  15.  
  16. int main()
  17. {
  18.     int n;
  19.     cin >> n;
  20.     int it = 1;
  21.     while (n != 0) {
  22.         vector<Point> arr(n); // массив со всеми точками из набора
  23.         map< pair<int, int>, string> table; //контейнер, для быстрого получения информации о существовании точки по координатам
  24.         vector<string> res; //динамический массив, в который будем складывать все прямоугольники из набора
  25.         for (int i = 0; i < n; ++i) { // считываем
  26.             cin >> arr[i].name >> arr[i].x >> arr[i].y;
  27.             table[{arr[i].x, arr[i].y}] = arr[i].name;
  28.         }
  29.  
  30.         for (int i = 0; i < n; ++i) { //перебираем все пары точек
  31.             for (int j = i + 1; j < n; ++j) {
  32.                 Point up_left = arr[i]; //будущая левая верхняя точка возможного прямоугольника
  33.                 Point down_right = arr[j]; //будущая права нижняя точка прямоугольника
  34.  
  35.                 if (down_right.x < up_left.x) { //поменяем местами, если не угадали, какая точка является левой верхней
  36.                     swap(down_right, up_left);
  37.                 }
  38.  
  39.                 if (up_left.x == down_right.x || up_left.y <= down_right.y) //отсекаем случаи, когда точки не на главной диагонали
  40.                     continue;
  41.                
  42.                 if (table.find({down_right.x, up_left.y}) != table.end() &&
  43.                     table.find({up_left.x, down_right.y}) != table.end()) { //если существуют точки симметричные относительно главной диагонали, образуемой данными, то значит, прямоугольник существует
  44.                     string rectangle = up_left.name + table[{down_right.x, up_left.y}] + down_right.name + table[{up_left.x, down_right.y}];
  45.                     res.push_back(rectangle);
  46.                 }
  47.             }
  48.         }
  49.        
  50.         sort(res.begin(), res.end()); //встроенная лексикографическая сортировка
  51.         cout << "Point set " << it << ':';
  52.         if (res.size()) { //Вывод
  53.             cout << "\n ";
  54.             for (int i = 0; i < res.size(); ++i) {
  55.                 cout << res[i] << ' ';
  56.                 if (!((i + 1) % 10) && (i != res.size() - 1)) {
  57.                     cout << endl;
  58.                 }
  59.             }
  60.         } else {
  61.             cout << ' ' << "No rectangles";
  62.         }
  63.         cout << endl;
  64.         cin >> n; //Считываем следующее число точек в наборе
  65.         ++it; //Обновляем счётчик набора
  66.     }
  67.  
  68.     return 0;
  69. }
Advertisement
Add Comment
Please, Sign In to add comment