3g-build-square.js

/*

G. Построить квадрат

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

Задано множество, состоящее из N различных точек на плоскости. Координаты всех точек — целые числа. Определите, какое минимальное количество точек нужно добавить во множество, чтобы нашлось четыре точки, лежащие в вершинах квадрата.

Формат ввода
В первой строке вводится число N (1 ≤ N ≤ 2000) — количество точек.
В следующих N строках вводится по два числа x[i], y[i] (-10^8 ≤ x[i], y[i] ≤ 10^8) — координаты точек.

Формат вывода
В первой строке выведите число K — минимальное количество точек, которые нужно добавить во множество.
В следующих K строках выведите координаты добавленных точек x[i], y[i] через пробел. Координаты должны быть целыми и не превышать 10^9 по модулю.
Если решений несколько — выведите любое из них.

Пример 1

Ввод
2
0 1
1 0

Вывод
2
0 0
1 1

Пример 2

Ввод
3
0 2
2 0
2 2

Вывод
1
0 0

Пример 3

Ввод
4
-1 1
1 1
-1 -1
1 -1

Вывод
0  

*/

const fs = require('fs');

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

const coordsSize = parseInt(input[0]);
const coordsMap = new Map();
const coordsArray = new Array(coordsSize);
let pointsToAdd = 4;
let secondPairAdded = false;
let pointsCoords = [];
const maxCoordValue = 1000000000;

for (let i = 1; i < input.length; ++i) {
    const [x, y] = input[i].trim().split(' ').map((value) => parseInt(value) * 2);
    const coordsPair = `${x} ${y}`;
    coordsMap.set(coordsPair, [x, y]);
    coordsArray[i - 1] = coordsPair;
}

if (coordsArray.length === 1) {
    if (coordsArray[0] !== '0 0') {
        coordsMap.set('0 0', [0, 0]);
        coordsArray.push('0 0');
    } else {
        coordsMap.set('2 2', [2, 2]);
        coordsArray.push('2 2');   
    }
    secondPairAdded = true;
}

mainLoop:
for (let i = 0; i < coordsArray.length; ++i) {
    const [x1, y1] = coordsMap.get(coordsArray[i]);
    for (let j = i + 1; j < coordsArray.length; ++j) {
        const [x2, y2] = coordsMap.get(coordsArray[j]);

        let xc = (x2 - x1) / 2;
        let yc = (y2 - y1) / 2;

        let x3;
        let y3;
        let x4;
        let y4;
        if (xc < 0 && yc < 0) {
            x3 = x1 + xc - yc;
            y3 = y1 + yc + xc;
            x4 = x1 + xc + yc;
            y4 = y1 + yc - xc;
        } else if (xc > 0 && yc < 0) {
            x3 = x1 + xc + yc;
            y3 = y1 + yc - xc;
            x4 = x1 + xc - yc;
            y4 = y1 + yc + xc;
        } else if (xc < 0 && yc > 0) {
            x3 = x1 + xc + yc;
            y3 = y1 + yc - xc;
            x4 = x1 + xc - yc;
            y4 = y1 + yc + xc;
        } else {
            x3 = x1 + xc - yc;
            y3 = y1 + yc + xc;
            x4 = x1 + xc + yc;
            y4 = y1 + yc - xc;
        }

        const hasCoords3 = coordsMap.has(`${x3} ${y3}`);
        const hasCoords4 = coordsMap.has(`${x4} ${y4}`);

        if (hasCoords3 && hasCoords4) {
            pointsToAdd = 0;
            pointsCoords = [];
            break mainLoop;
        } else if (hasCoords3 && pointsToAdd > 1) {
            pointsToAdd = 1;
            pointsCoords = [[x4, y4]];
        } else if (hasCoords4 && pointsToAdd > 1) {
            pointsToAdd = 1;
            pointsCoords = [[x3, y3]];
        } else if (pointsToAdd > 2) {
            if (
                x3 < maxCoordValue &&
                x3 % 2 === 0 &&
                y3 < maxCoordValue &&
                y3 % 2 === 0 &&
                x4 < maxCoordValue &&
                x4 % 2 === 0 &&
                y4 < maxCoordValue &&
                y4 % 2 === 0
            ) {
                pointsToAdd = 2;
                pointsCoords = [[x3, y3], [x4, y4]];
            }
        }
    }
}

if (secondPairAdded) {
    ++pointsToAdd;
    pointsCoords.push(coordsMap.get(coordsArray[1]));
}

pointsCoords = pointsCoords.map(([x, y]) => `${x / 2} ${y / 2}`);

const result = `${pointsToAdd}\n${pointsCoords.join('\n')}`;

fs.writeFileSync('output.txt', result);