Рациональная площадь

[Побережный Александр]

Докажите:
1. Площадь многоугольника, вершины которого лежат в узлах координатной сетки, имеет целое или полуцелое значение.
2. Площадь многоугольника, вершины которого имеют рациональные координаты, также будет иметь рациональное значение.

[grizzly]

Если сделать нарезку многоугольника на треугольники, посчитать площади по координатным формулам и сложить, получим оба пункта. Предполагались какие-то ограничения на уровень знаний? (или в чём олимпиадность?)

[Побережный Александр]

Конечно ограничения на уровень знаний предполагалось! Мне показалось, что уровню школьников это подойдет.

[grizzly]

Побережный Александр в сообщении #1210978 писал(а):

Мне показалось, что уровню школьников это подойдет.

А школьники в каком классе? Они поймут, что речь идёт о выпуклом многоугольнике? Если они знают, что существуют невыпуклые, то такая задача им вряд ли по силам. (Хорошо хоть о самопересечениях здесь не нужно думать.)

Да, для треугольника можно без всяких формул показать (полу)целость площади -- достроив нужным образом окаймляющий прямоугольник вырезав из него при необходимости другой. Предполагалось примерно такое решение? Согласен, для школьника это может быть интересной задачей.

[Побережный Александр]

grizzly в сообщении #1210996 писал(а):

Да, для треугольника можно без всяких формул показать (полу)целость площади -- достроив нужным образом окаймляющий прямоугольник вырезав из него при необходимости другой. Предполагалось примерно такое решение?

Именно такое решение и предполагалось.

Но почему вы сделали оговорку про невыпуклость? Для невыпуклых многоугольников все тоже работает, вроде...

[grizzly]

Побережный Александр в сообщении #1211006 писал(а):

Для невыпуклых многоугольников все тоже работает, вроде...

Конечно (в отличие от самопересекающихся). Я сделал оговорку, поскольку уровень сложности этих задач несопоставим: доказать (полу)целостность площади и доказать, что невыпуклый многоугольник можно триангулировать. Или Вы знаете школьное решение для такой триангуляции?

[Побережный Александр]

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

[slavav]

grizzly в сообщении #1211010 писал(а):

Побережный Александр в сообщении #1211006 писал(а):

Для невыпуклых многоугольников все тоже работает, вроде...

Конечно (в отличие от самопересекающихся). Я сделал оговорку, поскольку уровень сложности этих задач несопоставим: доказать (полу)целостность площади и доказать, что невыпуклый многоугольник можно триангулировать. Или Вы знаете школьное решение для такой триангуляции?

Триангулировать не надо. Полуцелой является площадь трапеции у которой три стороны параллельны осям. Из таких трапеций составляется любой многоугольник, хотя иногда придётся вычетать площади.

[grizzly]

Побережный Александр в сообщении #1211014 писал(а):

Затем вся область, которая не является многоугольником, разбивается на прямоугольные треугольники и прямоугольники

Это нужно доказывать. Вообще говоря, эта область может быть устроена достаточно сложно.

-- 20.04.2017, 14:52 --

slavav в сообщении #1211038 писал(а):

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

Вершины всех трапеций имеют целочисленные координаты, конечно? А как доказать, что любой многоугольник допускает такую "трапециляцию"?

[slavav]

grizzly в сообщении #1211049 писал(а):

Вершины всех трапеций имеют целочисленные координаты, конечно? А как доказать, что любой многоугольник допускает такую "трапециляцию"?

Это не нужно. Между любой стороной и осью абсцисс строите такую трапецию. Если сторона идёт "слева-направо" берёте её площадь с минусом, иначе с плюсом. Сумма площадей - есть площадь многоугольника (со знаком).
Как доказать это доказать? Разрежем всю плоскость на единичные клетки. Если клетка не целиком внутри или снаружи по отношению к многоугольнику, то разрежем её на несколько частей - одни целиком внутри, другие снаружи. Докажем что если "клетка" внутри многоугольника, то есть ровно нечётное число трапеций которые её содержат, причём положительных на одну больше чем отрицательных. Если клетка снаружи, то таких трапеций чётное число, половина с плюсом, половина с минусом.
К сожалению, моё доказательство привлекает понятие "внутри", которое без топологии строго не определишь. Но можно обойтись "очевидным" заменителем: будем говорить что точка внутри многоугольника, если вертикальный направленный вниз луч пересекает границу многоугольника нечётное число раз. Это дырявое определение, но дыры можно закрыть на школьном уровне.

[grizzly]

slavav
Спасибо, это рассуждение достойно олимпиадного.

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

[slavav]

Вы правы. Площадь со знаком можно определить для любой замкнутой ломаной. Определить и придать некоторый "физический" смысл. Такая площадь будет отвечать всем аксиомам обычной площади, кроме неотрицательности.

[worm2]

slavav в сообщении #1211089 писал(а):

Как доказать это доказать?

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

[ИСН]

У самопересекающихся будет две разных площади, одинаково естественные: аналоги "even-odd rule" и "nonzero rule". Для одной из них прокатывает без изменений рассуждение о трапециляции. Для другой нет.

[worm2]

ИСН в сообщении #1211150 писал(а):

Для другой нет.

Для другой само утверждение (первое) перестаёт быть верным. Это легко видеть, если сообразить, что площадь самопересечения можно сделать сколь угодно малой.