2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки





Начать новую тему Ответить на тему
 
 Суммарная длина целочисленной сетки внутри многоугольника
Сообщение02.05.2015, 01:44 


08/09/13
174
На плоскости задан произвольный многоугольник без самопересечений (однако не обязательно выпуклый). Вершин у многоугольника до ${10}^{5}$ и координаты всех вершин целые.
Задаётся прямоугольник простым перечислением вершин в том порядке, в котором они в нём связаны.

Рассмотрим бесконечную целочисленную сетку на плоскости, то есть сетку с узлами в точках с целыми координатами, линии которой идут по точкам, хотя бы одна из координат которых цела. Короче, обычную сетку из квадратиков с узлами в целых точках.
Требуется для заданного многоугольника найти суммарную длину линий сетки, которые лежат внутри этого многоугольника.

Я, кажется, основную идею просёк. Задача вполне тривиальна для прямоугольника и для прямоугольного треугольника (если включать в суммарную длину также длины сторон многоугольника, лежащих ровно на линии сетки - а это кажеться удобным делать, потом их всё равно можно вычесть за один проход). Воспользовавшись этим можно также посчитать ответ для выпуклого многоугольника (потому что это суть прямоугольник, из которого повычитали прямоугольники и прямоугольные треугольники).

Остаётся последний вопрос: как разложить произвольный многоугольник на сумму выпуклых? Интуитивно ясно, что такое разложение всегда существует, и на коленке даже можно набросать какие-то алгоритмы, но получается криво и громоздко. Прошу подсказки по поводу каких-то общих техник - наверняка случай возникновения этой задачи не единичен.

 Профиль  
                  
 
 Re: Суммарная длина целочисленной сетки внутри многоугольника
Сообщение02.05.2015, 14:05 
Заслуженный участник
Аватара пользователя


01/08/06
2153
Уфа
Если договориться, что линия сетки, лежащая ровно на границе многоугольника, считается с половинным коэффициентом, то ответ на вопрос задачи — это удвоенная площадь многоугольника. Доказывается так, как Вы написали: сначала для прямоугольника, потом для прямоугольного треугольника, затем как бы ни разбивался многоугольник на прямоугольные треугольники, результат всё равно один и тот же.

Если по поводу линий сетки, идущих точно по границе, договариваться как-то по-другому, то нужно научиться находить длину таких линий (это мне представляется совсем простой подзадачей), и дело в шляпе.

 Профиль  
                  
 
 Re: Суммарная длина целочисленной сетки внутри многоугольника
Сообщение02.05.2015, 18:48 


08/09/13
174
Ух ты как! Хитро... Очень поучительная задачка. То есть решение - это площадь минус половина длины сторон многоугольника на сетке...
Выходит, задача свелась к нахождению площади многоугольника. А как находить её теперь? Опять же, для выпуклого более-менее можно что-то придумать, а для произвольного непонятно... Всё равно придётся, значит, раскладывать в сумму выпуклых?
Из весёлых приёмчиков знаю только теорему Пика, но там нужно количество целых точек внутри. А это количество находить, кажется, не менее сложно, чем площадь.

 Профиль  
                  
 
 Re: Суммарная длина целочисленной сетки внутри многоугольника
Сообщение05.05.2015, 09:40 
Заслуженный участник
Аватара пользователя


01/08/06
2153
Уфа
Если честно, я от Вас узнал про теорему Пика. Это слишком сложно. Выражение для площади многоугольника через координаты его вершин очень простое. И годится для любого несамопересекающегося многоугольника (не обязательно с целочисленными координатами).
Я так думаю, олимпиадники должны эту формулу знать, ибо без неё тяжко.
Вот, в Википедии она есть.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 4 ] 

Модераторы: maxal, Karan, Toucan, PAV, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group