#include <iostream>
#include <Windows.h>
#include <vector>
#include <string>
#include  <iomanip>
#include <algorithm>
using namespace std;

vector<vector<int>> moves;
vector<vector<vector<int>>> a3;
vector < vector <int> > act;

void backTracking(int pos, vector < vector <int> >& act)
{
	bool isAdded = false;
	for (int i = 0; i < act.size(); i++) {
		bool isFound = false;
		for (const auto& it : moves)
			if (it == act[i]) {
				isFound = true;
				break;
			}
		if (!isFound) {
			moves.push_back(act[i]);
			backTracking(pos + 1, act);
		}
	}
	if (!moves.empty())
		a3.push_back(moves);
	if (!moves.empty())
		moves.pop_back();
}

int main()
{
	SetConsoleCP(1251); SetConsoleOutputCP(1251);
	cout << "Вводите координаты точек через пробел." << endl;
	vector<int> a;
	int t;
	cout << "По окончание ввода введите пустую строку." << std::endl;
	do {
		cin >> t;
		a.push_back(t);
	} while (getchar() != '\n');
	int n = a.size();
	sort(a.begin(), a.end());
	cout << "Вводите координаты начала и конца прямых." << endl;
	vector<int> b;
	vector<int> c;
	int t1, t2;
	do {
		cin >> t1 >> t2;
		b.push_back(t1);
		c.push_back(t2);
		cout << endl;
	} while (getchar() != '\n');
	int k = b.size();
	int** aa = new int* [n];
	for (int i = 0; i < n; i++) {
		aa[i] = new int[k];
		for (int i1 = 0; i1 < k; i1++)
			aa[i][i1] = 0;
	}
	int p = 0, min = n, r;
	for (int i = 0; i < n; i++) {
		for (int i1 = 0; i1 < k; i1++) {
			if ((a[i] >= b[i1]) && (a[i] <= c[i1])) {
				p++;
				aa[i][i1] = 1;
			}
		}
		if (p == 0) {
			cout << "Не покроет";
			exit;
		}
		if (p < min) {
			min = p;
			r = i;
		}
		p = 0;
	}
	cout << "Массив пересечений:" << endl;
	for (int i = 0; i < n; ++i) {
		for (int i1 = 0; i1 < k; ++i1) {
			cout << aa[i][i1] << ' ';
		}
		cout << endl;
	}
	vector < vector <int> > act(k, vector <int>(n));
	cout << endl;
	cout << "Векторы: " << endl;
	for (int i = 0; i < k; i++) {
		for (int i1 = 0; i1 < n; i1++) {
			act[i][i1] = aa[i1][i];
			cout << act[i][i1];
		}
		cout << endl;
	}
	backTracking(0, act);

	cout << endl;
	size_t counter = 1;
	for (size_t i = 0; i < a3.size(); i++)
	{
		cout << counter++ << ") ";
		for (size_t j = 0; j < a3[i].size(); j++)
		{
			for (size_t l = 0; l < a3[i][j].size(); l++)
			{
				cout << setw(2) << a3[i][j][l];
			}
			if (j + 1 < a3[i].size())
				cout << " -";
		}
		cout << endl;
	}
	return 0;
}