Автор: Мёнин›
« : 22/05/2017, 10:35:29 »Да, супермен летает напрямик, иначе задачи вообще нет.
Новости:
В тестовом режиме открыт раздел сайта «Конвенты».
Здесь больше нет рекламы. Но могла бы быть, могла.
Автор: Kэt›
« : 22/05/2017, 09:43:27 »Супермен летает по улицам или над ними?
Автор: Мёнин›
« : 21/05/2017, 01:31:05 »Задача школьного уровня
Супергерои Флэш и Супермен бегают наперегонки по Манхэттену, все улицы которого составляют точную перпендикулярную сетку без пропусков
Цель — оббежать заданные флажки на карте, все флажки стоят на перекрёстках.
Флэш бегает по улицам на 42% быстрее, чем Супермен летает. Кто победит в гонке, если и Флеш, и Супермен достаточно умны?
Супергерои Флэш и Супермен бегают наперегонки по Манхэттену, все улицы которого составляют точную перпендикулярную сетку без пропусков
Цель — оббежать заданные флажки на карте, все флажки стоят на перекрёстках.
Флэш бегает по улицам на 42% быстрее, чем Супермен летает. Кто победит в гонке, если и Флеш, и Супермен достаточно умны?
Автор: Мёнин›
« : 28/01/2017, 16:32:11 »А, то есть это и есть частный случай формулы Пика, который я внезапно эмпирически обнаружил, не зная общего.
Да, действительно, очевидная формула.
Да, действительно, очевидная формула.
Автор: 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
Решение требует знания формулы Пика: "Площадь клетчатого многоугольника (многоугольника, все вершины которого расположены в узлах клетчатой решетки) может быть вычислена по формуле
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
Автор: Мёнин›
« : 03/05/2016, 20:31:58 »Три возможных (разумеется, далеко не все возможные) многоугольника Q, проходящих через все нужные точки прямоугольника 5х5.
В первых двух случаях выполненность формулы очевидна.
Третий случай — когда все целевые точки — углы 36-угольника Q. И формула верна по-прежнему, но почему? Любые изменения этой формы без нарушения правил не меняют площадь. Но обосновать?
В первых двух случаях выполненность формулы очевидна.
Третий случай — когда все целевые точки — углы 36-угольника Q. И формула верна по-прежнему, но почему? Любые изменения этой формы без нарушения правил не меняют площадь. Но обосновать?
Автор: Мёнин›
« : 03/05/2016, 20:22:48 »это можно сделать лишь одним способом - змейкой, изменяя направление после каждой точки на 90 градусов. тогда и площадь соотв. можно посчитать только одним способом - но это тривиальная задача, может, я не понял чегоЗмейкой, да, но почему только кратные 90 градусов? Можно и кратные 45 градусов, и некоторые другие. Сейчас нарисую.
Автор: Adenis›
« : 03/05/2016, 13:20:17 »ну то есть змейка может быть и с поворотом не после каждой точки, а линия до конца след.стороны прямоугольника, потом поворот в обратн.сторону. Суть та же
Автор: Adenis›
« : 03/05/2016, 00:50:56 »Не понимаю условия, в общем. Как может быть одновременно "стороны которого проходят через все точки углов клеток, включая его границу" и "при этом углами которого могут являться только названные точки (например, все такие точки)". Что значит - "например"?
Есть множество точек, расположенных так, что они могут быть соединены параллельными друг другу вертикальными и паралельными друг другу горизонтальными линиями, при этом не останется ни одной несоединенной точки. Отрезки четырех линий образуют прямоугольник. Теперь, если стоит задача соединить ломаной кривой все точки внутри прямоугольника (включая те, что на его сторонах), это можно сделать лишь одним способом - змейкой, изменяя направление после каждой точки на 90 градусов. тогда и площадь соотв. можно посчитать только одним способом - но это тривиальная задача, может, я не понял чего
Есть множество точек, расположенных так, что они могут быть соединены параллельными друг другу вертикальными и паралельными друг другу горизонтальными линиями, при этом не останется ни одной несоединенной точки. Отрезки четырех линий образуют прямоугольник. Теперь, если стоит задача соединить ломаной кривой все точки внутри прямоугольника (включая те, что на его сторонах), это можно сделать лишь одним способом - змейкой, изменяя направление после каждой точки на 90 градусов. тогда и площадь соотв. можно посчитать только одним способом - но это тривиальная задача, может, я не понял чего
Автор: Мёнин›
« : 03/05/2016, 00:09:35 »Нет. Кривая Q по условию проходит через ВСЕ точки углов клеток, с АхВ он совпадает при А=1 или В=1, для которого случая формула верна очевидно.
Исправил некорректности в условии.
"стороны которого проходят через все точки внутри данного прямоугольника"Речь о клеточной тетради, я это, видимо, показал недостаточно ясно. Точки углов клеток, т.е. отмеченные геометрией тетради.
Не понимаю... точек внутри области конечной плоскости ведь континуум?
Исправил некорректности в условии.
Автор: Adenis›
« : 02/05/2016, 22:20:07 »формулировка "включая его границу" позволяет построить многоугольник, совпадающий с исходным прямоугольником, формула для этого случая неверна.
Автор: Alex The Owl›
« : 02/05/2016, 20:04:18 »"стороны которого проходят через все точки внутри данного прямоугольника"
Не понимаю... точек внутри области конечной плоскости ведь континуум?
Не понимаю... точек внутри области конечной плоскости ведь континуум?
Автор: Мёнин›
« : 01/05/2016, 16:28:04 »Возьмём в обычной клетчатой тетради прямоугольник AxB клеток, где A и B натуральные.
Построим произвольный многоугольник Q (замкнутую несамопересекающуюся ломаную), стороны которого проходят через все точки углов клеток внутри данного прямоугольника, включая его границу и углами которого могут являться только названные точки (например, все такие точки).
Можно ли доказать, что площадь Q = A*B - (A-1)*(B-1)/2 клеток?
То, что это эмпирически так, можете убедиться самостоятельно
UPD: исправил неточно данное условие.
Построим произвольный многоугольник Q (замкнутую несамопересекающуюся ломаную), стороны которого проходят через все точки углов клеток внутри данного прямоугольника, включая его границу и углами которого могут являться только названные точки (например, все такие точки).
Можно ли доказать, что площадь Q = A*B - (A-1)*(B-1)/2 клеток?
То, что это эмпирически так, можете убедиться самостоятельно
UPD: исправил неточно данное условие.