algoprog.kz

В игре в крестики-нолики всегда можно сыграть в ничью. Если листке бумаге нарисовать все состояния игры, то можно вывести стратегию для каждого игрока. Самое главное это первые два-три хода, дальше либо игра приходит в тупиковое состояние(ничья) и надо лишь правильно доиграть до конца, либо один из игроков сделал ошибку и можно сделать выигрышный ход.

За крестики:

Сделать первый ход в центральное поле. Противник может ответить ходом либо в угол, либо на сторону поля.

• Если противник ответил ходом в угловое поле — сходить в ответ в противоположный угол. Если противник ответил ходом на сторону — он проиграл. Следует ответить ходом в один из двух несоседних углов. Чтобы не проиграть, противник должен занять один из углов. Дальнейшие ходы делаются так, чтобы блокировать построение тройки противником. — Ничья.
• Если противник ответил ходом на сторону — он проиграл. Следует ответить ходом в один из двух несоседних углов. Противник будет вынужден пойти в противоположный угол, чтобы на следующем ходу не проиграть. Сходить в оставшийся пустым угол, соседний с первым ходом противника. В результате блокируется построение тройки противником, а крестики образуют треугольник — получится «вилка», позволяющая следующим ходом построить тройку двумя способами. Как бы ни ответил противник, следующим ходом строится одна из троек. — Выигрыш.

За нолики:

• Если противник сходил первым ходом в центр, ответить ходом в любой из углов, затем каждым следующим ходом блокировать возможность построения противником очередной тройки, при возможности выбора предпочитая ходы в углы. — Ничья. Или заканчивая свою тройку при удобном случае. — Выигрыш.
• Если противник сходит первым ходом не в центр, ответить ходом в центр. Если ответным ходом противник займёт два противоположных угла, ответить ходом на сторону. Затем каждым следующим ходом блокировать возможность построения противником очередной тройки, при возможности выбора предпочитая ходы в углы. — Ничья.

Задача решается перебором. Перебираем три точки и проверяем на условие прямоугольности.

Проверять на прямоугольность надо аккуратно. Так как времени хватает почти в притык. Известно, что вычисления из под корня работают долго, так-что по возможности желательно их не делать. Известно, что у прямоугольного треугольника гипотенуза $h = \sqrt{a^2 + b^2}$.

Так-как нам известны координаты трех точек на плоскости $(x_1, y_1), (x_2, y_2), (x_3, y_3)$, то посчитать длинны сторон треуголника (x, y, z) не сложно.

• $x = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$
• $y = \sqrt{(x_1 - x_3)^2 + (y_1 - y_3)^2}$
• $z = \sqrt{(x_2 - x_3)^2 + (y_2 - y_3)^2}$

Понятно, что если рассматриваемый треугольник является прямоуголным, то должно выполняться одно из условий:

• $x^2 = y^2 + z^2$
• $y^2 = x^2 + z^2$
• $z^2 = y^2 + x^2$

Для вычисления x мы берем выражение $(x_1 - x_2)^2 + (y_1 - y_2)^2$ под корнем, а потом при сравнениии опять берем квадрат. Очевидно, что это лишнее и тут можно сократить вычисления из под корня вычисляя только:

• $x' = (x_1 - x_2)^2 + (y_1 - y_2)^2 = \sqrt{x}$
• $y' = (x_1 - x_3)^2 + (y_1 - y_3)^2 = \sqrt{y}$
• $z' = (x_2 - x_3)^2 + (y_2 - y_3)^2 = \sqrt{z}$

и проверять условия так:

• $x' = y' + z'$
• $y' = x' + z'$
• $z' = y' + x'$

если одно из условий выполняется, то треугольник прямоугольный и мы определили какая сторона у наc гипотенуза, а какие катеты. Предположим у нас выполнилось первое условие. Дальше надо еще проверить площадь треуголника $A = \frac{a*b}{2}$.

Мы уже посчитали $y' = a^2$ и $z' = b^2$, тогда А можно считать так $A = \frac{\sqrt{y'} * \sqrt{z'}}{2}$, но лучше так $A = \sqrt{\frac{y' * z'}{4}}$. Если и это условие $A_1 \le A \le A_2$ выполняется, то увеличиваем счетчик на один. Когда перебор завершится, то выписываем что насчитали.

А вообще можно посчитать площадь в квадрате $A^2 = \frac{y' * z'}{4}$ и сравнивать $A_1^2 \le A^2 \le A_2^2$. Но тут надо аккуратнее так-как может быть большим. $A^2 > 2^{31}$