Тема: Геометрия клеточной тетради (сложные задачи)

[Мёнин›]

Возьмём в обычной клетчатой тетради прямоугольник AxB клеток, где A и B натуральные.
Построим произвольный многоугольник Q (замкнутую несамопересекающуюся ломаную), стороны которого проходят через все точки углов клеток внутри данного прямоугольника, включая его границу и углами которого могут являться только названные точки (например, все такие точки).

Можно ли доказать, что площадь Q = A*B - (A-1)*(B-1)/2 клеток?
То, что это эмпирически так, можете убедиться самостоятельно

UPD: исправил неточно данное условие.

[Alex The Owl›]

"стороны которого проходят через все точки внутри данного прямоугольника"
Не понимаю... точек внутри области конечной плоскости ведь континуум?

[Adenis›]

формулировка "включая его границу" позволяет построить многоугольник, совпадающий с исходным прямоугольником,  формула для этого случая неверна.

[Мёнин›]

Нет. Кривая Q по условию проходит через ВСЕ точки углов клеток, с АхВ он совпадает при А=1 или В=1, для которого случая формула верна очевидно.

"стороны которого проходят через все точки внутри данного прямоугольника"
Не понимаю... точек внутри области конечной плоскости ведь континуум?

Речь о клеточной тетради, я это, видимо, показал недостаточно ясно. Точки углов клеток, т.е. отмеченные геометрией тетради.

Исправил некорректности в условии.

[Adenis›]

Не понимаю условия, в общем. Как может быть одновременно "стороны которого проходят через все точки углов клеток, включая его границу" и "при этом углами которого могут являться только названные точки (например, все такие точки)". Что значит - "например"?

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

[Adenis›]

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

[Мёнин›]

это можно сделать лишь одним способом - змейкой, изменяя направление после каждой точки на 90 градусов. тогда и площадь соотв. можно посчитать только одним способом - но это тривиальная задача, может, я не понял чего

Змейкой, да, но почему только кратные 90 градусов? Можно и кратные 45 градусов, и некоторые другие. Сейчас нарисую.

[Мёнин›]

Три возможных (разумеется, далеко не все возможные) многоугольника Q, проходящих через все нужные точки прямоугольника 5х5.
В первых двух случаях выполненность формулы очевидна.

Третий случай — когда все целевые точки — углы 36-угольника Q. И формула верна по-прежнему, но почему? Любые изменения этой формы без нарушения правил не меняют площадь. Но обосновать?

[theMULYAman›]

Я знаю, что вопрос очень давний, но все же...

Решение требует знания формулы Пика: "Площадь клетчатого многоугольника (многоугольника, все вершины которого расположены в узлах клетчатой решетки) может быть вычислена по формуле

S = I + B/2 - 1

где I - количество узлов внутри многоугольника, B - количество узлов на границе.

Тогда данная задача решается в одну строку, так как эта кривая Q образует многоугольник, у которого I=0 (внутри узлов нет), B=(A+1)(B+1) (все узлы многоугольника), тогда его площадь:

S = 0 + (A+1)(B+1)/2 - 1 = AB/2 + A/2 + B/2 + 1/2 - 1 = AB - (AB/2 - A/2 - B/2 + 1/2) = AB - (A-1)(B-1)/2

[Мёнин›]

А, то есть это и есть частный случай формулы Пика, который я внезапно эмпирически обнаружил, не зная общего.
Да, действительно, очевидная формула.

[Мёнин›]

Задача школьного уровня

Супергерои Флэш и Супермен бегают наперегонки по Манхэттену, все улицы которого составляют точную перпендикулярную сетку без пропусков
Цель — оббежать заданные флажки на карте, все флажки стоят на перекрёстках.
Флэш бегает по улицам на 42% быстрее, чем Супермен летает. Кто победит в гонке, если и Флеш, и Супермен достаточно умны?

[Kэt›]

Супермен летает по улицам или над ними?

[Мёнин›]

Да, супермен летает напрямик, иначе задачи вообще нет.