3h-matches-are-not-toys.js

/*

H. Спички детям не игрушка!

Ограничение времени	3 секунды (фактическое использование на тестах – до 2.213s)
Ограничение памяти	256Mb (фактическое использование на тестах – до 130.54Mb)
Ввод	стандартный ввод или input.txt
Вывод	стандартный вывод или output.txt

Вася любит решать головоломки со спичками. Чаще всего они формулируется следующим образом: дано изображение A, составленное из спичек; переложите в нем минимальное количество спичек так, чтобы получилось изображение B.

Например, из номера текущего командного чемпионата школьников Санкт-Петербурга по программированию, можно получить ромб с диагональю, переложив всего три спички.

Головоломки, которые решает Вася, всегда имеют решение. Это значит, что набор спичек, используемый в изображении A, совпадает с набором спичек, используемым в изображении B. Кроме того, в одном изображении никогда не встречаются две спички, у которых есть общий участок ненулевой длины (то есть спички могут пересекаться, но не могут накладываться друг на друга).

Вася устал решать головоломки вручную, и теперь он просит вас написать, программу, которая будет решать головоломки за него. Программа будет получать описания изображений A и B и должна найти минимальное количество спичек, которые надо переложить в изображении A, чтобы полученная картинка получалась из B параллельным переносом.

Формат ввода
В первой строке входного файла содержится целое число n — количество спичек в каждом из изображений (1 ≤ n ≤ 1000).
В следующих n строках записаны координаты концов спичек на изображении A. Спичка номер i описывается целыми числами x[1][i], y[1][i], x[2][i], y[2][i] — координатами ее концов. Следующие n строк содержат описание изображения B в таком же формате. Набор длин этих спичек совпадает с набором длин спичек с изображения A.
Все координаты по абсолютной величине не превосходят 10^4. Все спички имеют ненулевую длину, то есть x[1][i] ≠ x[2][i] или y[1][i] ≠ y[2][i].

Формат вывода
Выведите в выходной файл минимальное количество спичек, которые следует переложить, чтобы изображение A совпало с изображением B, с точностью до параллельного переноса.

Пример 1

Ввод
5
0 0 1 2
1 0 0 2
2 0 2 2
4 0 3 2
4 0 5 2
9 -1 10 1
10 1 9 3
8 1 10 1
8 1 9 -1
8 1 9 3

Вывод
3

Пример 2

Ввод
1
3 4 7 9
-1 3 3 8

Вывод
0

Пример 3

Ввод
1
-4 5 2 -3
-12 4 -2 4

Вывод
1

*/

const fs = require('fs');

const input = fs.readFileSync('input.txt', 'utf8').toString().trim().split('\n');

const totalMatchsticks = parseInt(input[0]);

const dataMap = new Map();

for (let i = 1; i < input.length; ++i) {
    const [x1, y1, x2, y2] = input[i].trim().split(' ').map((value) => parseInt(value) * 2);

    const xv = (x2 - x1) / 2;
    const yv = (y2 - y1) / 2;
    const xc = x1 + xv;
    const yc = y1 + yv;

    let vectors = '';
    if (yv === 0) {
        vectors = `${Math.abs(xv)} ${yv}`;
    } else if (yv < 0) {
        vectors = `${-xv} ${-yv}`;
    } else {
        vectors = `${xv} ${yv}`;
    }

    const coords = [xc, yc];

    let entry = dataMap.get(vectors);
    if (!entry) {
        entry = {
            sourceCoords: [],
            targetCoords: [],
        };
        dataMap.set(vectors, entry);
    }

    if (i <= totalMatchsticks) {
        entry.sourceCoords.push(coords);
    } else {
        entry.targetCoords.push(coords);
    }
}

const parallelShiftMap = {};
let maxOccurrences = 0;

dataMap.forEach((entry) => {
    if (entry.sourceCoords.length === 0 || entry.targetCoords.length === 0) {
        return;
    }

    for (const [sx, sy] of entry.sourceCoords) {
        for (const [tx, ty] of entry.targetCoords) {
            const parallelShiftVector = `${sx - tx} ${sy - ty}`;
            parallelShiftMap[parallelShiftVector] = (parallelShiftMap[parallelShiftVector] || 0) + 1;
            if (parallelShiftMap[parallelShiftVector] > maxOccurrences) {
                maxOccurrences = parallelShiftMap[parallelShiftVector];
            }
        }
    }
});

const result = totalMatchsticks - maxOccurrences;

fs.writeFileSync('output.txt', `${result}`);