Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <map>
- #include <string>
- #include <algorithm>
- using namespace std;
- struct Point // структура точки
- {
- string name;
- int x;
- int y;
- };
- int main()
- {
- int n;
- cin >> n;
- int it = 1;
- while (n != 0) {
- vector<Point> arr(n); // массив со всеми точками из набора
- map< pair<int, int>, string> table; //контейнер, для быстрого получения информации о существовании точки по координатам
- vector<string> res; //динамический массив, в который будем складывать все прямоугольники из набора
- for (int i = 0; i < n; ++i) { // считываем
- cin >> arr[i].name >> arr[i].x >> arr[i].y;
- table[{arr[i].x, arr[i].y}] = arr[i].name;
- }
- for (int i = 0; i < n; ++i) { //перебираем все пары точек
- for (int j = i + 1; j < n; ++j) {
- Point up_left = arr[i]; //будущая левая верхняя точка возможного прямоугольника
- Point down_right = arr[j]; //будущая права нижняя точка прямоугольника
- if (down_right.x < up_left.x) { //поменяем местами, если не угадали, какая точка является левой верхней
- swap(down_right, up_left);
- }
- if (up_left.x == down_right.x || up_left.y <= down_right.y) //отсекаем случаи, когда точки не на главной диагонали
- continue;
- if (table.find({down_right.x, up_left.y}) != table.end() &&
- table.find({up_left.x, down_right.y}) != table.end()) { //если существуют точки симметричные относительно главной диагонали, образуемой данными, то значит, прямоугольник существует
- string rectangle = up_left.name + table[{down_right.x, up_left.y}] + down_right.name + table[{up_left.x, down_right.y}];
- res.push_back(rectangle);
- }
- }
- }
- sort(res.begin(), res.end()); //встроенная лексикографическая сортировка
- cout << "Point set " << it << ':';
- if (res.size()) { //Вывод
- cout << "\n ";
- for (int i = 0; i < res.size(); ++i) {
- cout << res[i] << ' ';
- if (!((i + 1) % 10) && (i != res.size() - 1)) {
- cout << endl;
- }
- }
- } else {
- cout << ' ' << "No rectangles";
- }
- cout << endl;
- cin >> n; //Считываем следующее число точек в наборе
- ++it; //Обновляем счётчик набора
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment