задачка

[avva]

Задача в виде теоремы, очень красивой по-моему, и не слишком сложной.
На плоскости с координатной сеткой нарисован многоугольник, все вершины которого лежат в узлах сетки. Стороны многоугольника не пересекаются друг с другом (но он необязательно выпуклый). Доказать, что площадь многоугольника равна i+e/2-1, где i - количество узлов сетки, находящихся внутри многоугольника, а e - количество узлов сетки, находящихся на его границе (включая его вершины).
Если кто-то знает, не подсказывайте ;-)

Comments

[ex-ilyavinar899.livejournal.com]

1. Для квадратика 1х1 это утверждение верно.

2. Если два прямоугольника соприкасаются отрезком длиной k, то в получившемся многоугольнике k-1 точек переходят из пограничных для обоих во внутренние, и еще две угловые пограничные точки считаются один раз, а не два - утверждение верно. Итак, утверждение верно для любой фигуры, составленной из квадратиков, но нас интересуют только прямоугольники.

3. Делим прямоугольник на два диагональю. Угловые точки считаются два раза, а не один; все точки на диагонали перестают быть внутренними, и становятся пограничными для двух фигур. Утверждение верно для прямоугольных треугольников со сторонами, параллельными осям координат.

4. Любой треугольник с вершинами в сетке можно вписать в прямоугольник; разница - прямоугольные треугольники со сторонами, параллельными осям координат. Утверждение верно для прямоугольника и для остаточных прямоугольных треугольников - значит, оно верно и для данного треугольника.

5. Разобъем многоугольник на треугольники, и начнем "сливать" их один за другим. Утверждение верно для каждого треугольника; при слиянии две пограничные точки становятся одной внутренней.

Ах, если бы задачка про карты так просто решалась!