Форум Tolkien.SU

Человек Играющий => Стол с зеленым сукном => Тема начата: Мёнин от 01/05/2016, 16:28:04

Название: Геометрия клеточной тетради (сложные задачи)
Отправлено: Мёнин от 01/05/2016, 16:28:04
Возьмём в обычной клетчатой тетради прямоугольник AxB клеток, где A и B натуральные.
Построим произвольный многоугольник Q (замкнутую несамопересекающуюся ломаную), стороны которого проходят через все точки углов клеток внутри данного прямоугольника, включая его границу и углами которого могут являться только названные точки (например, все такие точки).

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

UPD: исправил неточно данное условие.
Название: Геометрия клеточной тетради (сложные задачи)
Отправлено: Alex The Owl от 02/05/2016, 20:04:18
"стороны которого проходят через все точки внутри данного прямоугольника"
Не понимаю... точек внутри области конечной плоскости ведь континуум?
Название: Геометрия клеточной тетради (сложные задачи)
Отправлено: Adenis от 02/05/2016, 22:20:07
формулировка "включая его границу" позволяет построить многоугольник, совпадающий с исходным прямоугольником,  формула для этого случая неверна.
Название: Геометрия клеточной тетради (сложные задачи)
Отправлено: Мёнин от 03/05/2016, 00:09:35
Нет. Кривая Q по условию проходит через ВСЕ точки углов клеток, с АхВ он совпадает при А=1 или В=1, для которого случая формула верна очевидно.
"стороны которого проходят через все точки внутри данного прямоугольника"
Не понимаю... точек внутри области конечной плоскости ведь континуум?
Речь о клеточной тетради, я это, видимо, показал недостаточно ясно. Точки углов клеток, т.е. отмеченные геометрией тетради.

Исправил некорректности в условии.
Название: Геометрия клеточной тетради (сложные задачи)
Отправлено: Adenis от 03/05/2016, 00:50:56
Не понимаю условия, в общем. Как может быть одновременно "стороны которого проходят через все точки углов клеток, включая его границу" и "при этом углами которого могут являться только названные точки (например, все такие точки)". Что значит - "например"?

Есть множество точек, расположенных так, что они могут быть соединены параллельными друг другу вертикальными и паралельными друг другу горизонтальными линиями, при этом не останется ни одной несоединенной точки. Отрезки четырех линий образуют прямоугольник. Теперь, если стоит задача соединить ломаной кривой все точки внутри прямоугольника (включая те, что на его сторонах), это можно сделать лишь одним способом - змейкой, изменяя направление после каждой точки на 90 градусов. тогда и площадь соотв. можно посчитать только одним способом - но это тривиальная задача, может, я не понял чего
Название: Геометрия клеточной тетради (сложные задачи)
Отправлено: Adenis от 03/05/2016, 13:20:17
ну то есть змейка может быть и с поворотом не после каждой точки, а линия до конца след.стороны прямоугольника, потом поворот в обратн.сторону. Суть та же
Название: Геометрия клеточной тетради (сложные задачи)
Отправлено: Мёнин от 03/05/2016, 20:22:48
это можно сделать лишь одним способом - змейкой, изменяя направление после каждой точки на 90 градусов. тогда и площадь соотв. можно посчитать только одним способом - но это тривиальная задача, может, я не понял чего
Змейкой, да, но почему только кратные 90 градусов? Можно и кратные 45 градусов, и некоторые другие. Сейчас нарисую.
Название: Геометрия клеточной тетради (сложные задачи)
Отправлено: Мёнин от 03/05/2016, 20:31:58
Три возможных (разумеется, далеко не все возможные) многоугольника Q, проходящих через все нужные точки прямоугольника 5х5.
В первых двух случаях выполненность формулы очевидна.

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

(http://cs629112.vk.me/v629112127/15554/MBMDXmD7j_8.jpg)
Название: Геометрия клеточной тетради (сложные задачи)
Отправлено: theMULYAman от 28/01/2017, 00:10:30
Я знаю, что вопрос очень давний, но все же...

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

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
Название: Геометрия клеточной тетради (сложные задачи)
Отправлено: Мёнин от 28/01/2017, 16:32:11
А, то есть это и есть частный случай формулы Пика, который я внезапно эмпирически обнаружил, не зная общего.
Да, действительно, очевидная формула.
Название: Геометрия клеточной тетради (сложные задачи)
Отправлено: Мёнин от 21/05/2017, 01:31:05
Задача школьного уровня

Супергерои Флэш и Супермен бегают наперегонки по Манхэттену, все улицы которого составляют точную перпендикулярную сетку без пропусков
Цель — оббежать заданные флажки на карте, все флажки стоят на перекрёстках.
Флэш бегает по улицам на 42% быстрее, чем Супермен летает. Кто победит в гонке, если и Флеш, и Супермен достаточно умны?
Название: Геометрия клеточной тетради (сложные задачи)
Отправлено: Kэt от 22/05/2017, 09:43:27
Супермен летает по улицам или над ними?
Название: Геометрия клеточной тетради (сложные задачи)
Отправлено: Мёнин от 22/05/2017, 10:35:29
Да, супермен летает напрямик, иначе задачи вообще нет.