Author Topic: Геометрия клеточной тетради (сложные задачи)  (Read 3120 times)

0 Members and 1 Guest are viewing this topic.

Offline Мёнин

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

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

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

Offline Alex The Owl

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

Offline Adenis

  • Ветеран
  • *****
  • Gender: Male
  • O, sancta simplicitas!
    • View Profile
формулировка "включая его границу" позволяет построить многоугольник, совпадающий с исходным прямоугольником,  формула для этого случая неверна.

Offline Мёнин

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

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

Offline Adenis

  • Ветеран
  • *****
  • Gender: Male
  • O, sancta simplicitas!
    • View Profile
Не понимаю условия, в общем. Как может быть одновременно "стороны которого проходят через все точки углов клеток, включая его границу" и "при этом углами которого могут являться только названные точки (например, все такие точки)". Что значит - "например"?

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

Offline Adenis

  • Ветеран
  • *****
  • Gender: Male
  • O, sancta simplicitas!
    • View Profile
ну то есть змейка может быть и с поворотом не после каждой точки, а линия до конца след.стороны прямоугольника, потом поворот в обратн.сторону. Суть та же

Offline Мёнин

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

Offline Мёнин

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

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

« Last Edit: 03/05/2016, 20:51:31 by Мёнин »

theMULYAman

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

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

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

Offline Мёнин

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

Offline Мёнин

  • кристофер-толкинист
  • Мафия
  • **********
  • Gender: Male
  • посмотри в глаза чудовищ
    • View Profile
Задача школьного уровня

Супергерои Флэш и Супермен бегают наперегонки по Манхэттену, все улицы которого составляют точную перпендикулярную сетку без пропусков
Цель — оббежать заданные флажки на карте, все флажки стоят на перекрёстках.
Флэш бегает по улицам на 42% быстрее, чем Супермен летает. Кто победит в гонке, если и Флеш, и Супермен достаточно умны?
« Last Edit: 21/05/2017, 09:56:59 by Мёнин »

Offline Kэt

  • путаннная девочка
  • Ветеран
  • *****
  • Gender: Female
  • Вчера я была я и все шло как обычно... (c)
    • View Profile
Супермен летает по улицам или над ними?
- А почему это место - Очень Странное Место?
- А потому, что все остальные места очень уж нестранные. Должно же быть хоть одно Очень Странное Место...

Offline Мёнин

  • кристофер-толкинист
  • Мафия
  • **********
  • Gender: Male
  • посмотри в глаза чудовищ
    • View Profile
Да, супермен летает напрямик, иначе задачи вообще нет.