/*
Описание алгоритма.
Исходя из условий задания, независимо от размера сетки, в любой линии (горизонтальной, вертикальной, диагональной) можно расположить не более двух узлов.Таким образом, независимо от варианта расстановки узлов, их общее количество не может превышать N * 2.
Наивное решение задачи заключается в переборе всех возможных вариантов расстановки N * 2 узлов в сетке размером N * N, например, для сетки размером 8 * 8 это значение равно числу сочетаний из 64 по 16, то есть 488526937079580.
В данном решении для оптимизации алгоритма использовался поиск с возвратом и кэширование данных.Сетка рассматривается как матрица размером N * N.
Работа функции get_count начинается с поиска места для размещения точки с первого столбца первой строки матрицы.Если в строке и столбце, на пересечении которых находится ячейка, находится не более одного элемента, выполняется проверка функцией check_lines пересечения ячейки матрицы с существующими линиями, образованными любыми двумя точками.
Если точка не пересекается ни с одной линией:
-точка добавляется в массив points;
-по общему уравнению прямой рассчитываются и сохраняются в массиве lines параметры всех линий, образованных добавленной точкой с существующими точками;
-счетчик элементов для соответствующей строки и столбца увеличивается на единицу;
-выполняется рекурсивный запуск функции get_count для поиска места для добавления следующей точки, при этом поиск выполняется со следующего столбца в строке либо с начала следующей строки, если в текущую уже добавлены две точки.
После рекурсивной проверки возможности размещения оставшихся точек, последняя добавленная точка удаляется, линии, образованные ей удаляются, выполняется попытка размещения точки в следующей позиции строки для проверки другого варианта размещения.
Если удалось разместить все N*2 точек, счетчик result увеличивается на единицу, выполняется поиск варианта следующего размещения.
*/


#include <iostream>
#include <vector>

struct line {
    int A;
    int B;
    int C;
};

struct point {
    int x;
    int y;
};

int field_size, max_count, cnt = 0, result = 0;
std::vector<int> row, col;
std::vector<point> points;
std::vector<line> lines;

bool check_lines(const int x, const int y) {
    for (const auto& l : lines) {
        if (l.A * x + l.B * y + l.C == 0) {
            return false;
        }
    }
    return true;
}

void add_lines(const int x, const int y) {

    int A, B, C;

    for (const auto& p : points) {
        A = y - p.y;
        B = p.x - x;
        C = p.x * (p.y - y) + p.y * (x - p.x);
        lines.push_back({ A, B, C});
    }
}

void get_count(int i = 0, int k = 0) {
    for (int j = k; j < field_size; ++j) {
        if (row[i] < 2 && col[j] < 2 && check_lines(i, j)) {
            if (cnt == max_count - 1) {
                result++;
                return;
            }
            else {
                row[i]++;
                col[j]++;
                add_lines(i, j);
                points.push_back({ i, j });
                cnt++;

                row[i] == 2 ? get_count(i + 1, 0) : get_count(i, j + 1);

                row[i]--;
                col[j]--;
                lines.resize(lines.size() - (points.size() - 1));
                points.pop_back();
                cnt--;
            }
        }
    }
}

int main() {

    setlocale(LC_ALL, "ru");

    std::cout << "Введите размер сетки: ";

    std::cin >> field_size;

    max_count = field_size * 2;

    row.resize(field_size);
    col.resize(field_size);

    get_count();

    std::cout << "В сетке можно расположить максимум " << max_count << " точек" << std::endl;
    std::cout << "Количество расстановок из " << max_count << " точек: " << result << std::endl;

}