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

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн Мёнин

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

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

UPD: исправил неточно данное условие.
« Последнее редактирование: 03/05/2016, 20:50:52 от Мёнин »

Оффлайн Alex The Owl

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

Оффлайн Adenis

  • Ветеран
  • *****
  • Пол: Мужской
  • You've got mail
    • Просмотр профиля
формулировка "включая его границу" позволяет построить многоугольник, совпадающий с исходным прямоугольником,  формула для этого случая неверна.

Оффлайн Мёнин

  • кристофер-толкинист
  • Мафия
  • **********
  • Пол: Мужской
  • посмотри в глаза чудовищ
    • Просмотр профиля
Нет. Кривая Q по условию проходит через ВСЕ точки углов клеток, с АхВ он совпадает при А=1 или В=1, для которого случая формула верна очевидно.
"стороны которого проходят через все точки внутри данного прямоугольника"
Не понимаю... точек внутри области конечной плоскости ведь континуум?
Речь о клеточной тетради, я это, видимо, показал недостаточно ясно. Точки углов клеток, т.е. отмеченные геометрией тетради.

Исправил некорректности в условии.
« Последнее редактирование: 03/05/2016, 00:12:32 от Мёнин »

Оффлайн Adenis

  • Ветеран
  • *****
  • Пол: Мужской
  • You've got mail
    • Просмотр профиля
Не понимаю условия, в общем. Как может быть одновременно "стороны которого проходят через все точки углов клеток, включая его границу" и "при этом углами которого могут являться только названные точки (например, все такие точки)". Что значит - "например"?

Есть множество точек, расположенных так, что они могут быть соединены параллельными друг другу вертикальными и паралельными друг другу горизонтальными линиями, при этом не останется ни одной несоединенной точки. Отрезки четырех линий образуют прямоугольник. Теперь, если стоит задача соединить ломаной кривой все точки внутри прямоугольника (включая те, что на его сторонах), это можно сделать лишь одним способом - змейкой, изменяя направление после каждой точки на 90 градусов. тогда и площадь соотв. можно посчитать только одним способом - но это тривиальная задача, может, я не понял чего
« Последнее редактирование: 03/05/2016, 01:19:58 от Adenis »

Оффлайн Adenis

  • Ветеран
  • *****
  • Пол: Мужской
  • You've got mail
    • Просмотр профиля
ну то есть змейка может быть и с поворотом не после каждой точки, а линия до конца след.стороны прямоугольника, потом поворот в обратн.сторону. Суть та же

Оффлайн Мёнин

  • кристофер-толкинист
  • Мафия
  • **********
  • Пол: Мужской
  • посмотри в глаза чудовищ
    • Просмотр профиля
это можно сделать лишь одним способом - змейкой, изменяя направление после каждой точки на 90 градусов. тогда и площадь соотв. можно посчитать только одним способом - но это тривиальная задача, может, я не понял чего
Змейкой, да, но почему только кратные 90 градусов? Можно и кратные 45 градусов, и некоторые другие. Сейчас нарисую.

Оффлайн Мёнин

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

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

« Последнее редактирование: 03/05/2016, 20:51:31 от Мёнин »

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

Оффлайн Мёнин

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