Дано два выпуклых многоугольника C1 и C2. Требуется доказать, что существует прямая L, которая делит одновременно и C1 и C2 на две равные части.
Спасибо.
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
2 | maomao90 | 163 |
4 | atcoder_official | 161 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
9 | nor | 153 |
9 | Dominater069 | 153 |
Дано два выпуклых многоугольника C1 и C2. Требуется доказать, что существует прямая L, которая делит одновременно и C1 и C2 на две равные части.
Спасибо.
Название |
---|
Слегка сумбурное доказательство, но всё же:
Возьмём достаточно большую окружность, так чтобы оба многоугольника лежали внутри неё.
Возьмём некую точку A на окружности. И проведём из неё луч внутрь окружности. Очевидно, что функция зависимости площади одной из половин многоугольника, отрезаемой лучом, от угла наклона луча будет непрерывной и монотонной. А значит для данной точки A и многоугольника C будет существовать единственная точка B на окружности, такая что AB делит многоугольник пополам. Отсюда следует, что и функция зависимости положения точки B от точки A также непрерывна.
Вернёмся теперь к нашим двум многоугольникам . Докажем, что существует отрезок соединяющий две точки окружности, и делящий оба многоугольника пополам. Зафиксируем точку A на окружности, и возьмём соответствующие ей точки B1 и B2. Без ограничения общности, предположим что B2 лежит на дуге B1A.
Теперь давайте будем двигать первую точку по дуге AB1. Тогда вторая точка для первого многоугольника будет двигаться по дуге B1A и дойдёт до точки A, а для второго многоугольника — по дуге B2A, и до точки A не дойдёт (так как иначе б, точки B1 и B2 совпадали). Однако, так как точка B2 лежит на дуге B1A, и вторая точка первого многоугольника непрерывно прошла всю дугу B1A, то, очевидно, имел место момент, когда вторые точки для обоих многоугольников совпадали, что и требовалось доказать.
Рассмотрим функцию f(α), вычисляемую следующим образом.
Выпустим луч из начала координат под углом α. Параллельным переносом луча добьёмся того, чтобы соответствующая лучу прямая разбивала многоугольник C1 на две равные части (по непрерывности это возможно). Тогда f(α) = Sleft - Sright — разность площадей частей многоугольника C2, оказавшихся слева и справа от луча, соответственно.
Теперь осталось заметить, что если f(α) = 0 для некоторого α, то искомая прямая найдена, а также то, что f(0) = - f(π) — значит, по непрерывности функции f такое α существует на отрезке [0;π].