На плоскости задана незамкнутая ломаная. Никакие две ее вершины не совпадают. Требуется найти прямую, пересекающую максимальное количество последовательных звеньев. Пересечение звена - это пересечение его ровно в одной внутренней точке.
N - количество вершин ломаной (2 ? N ? 2000)
1 2010-03-04 14:35:09
Тема: Ломаная (2 ответов, оставленных в Problems)
2 2010-03-02 06:20:07
Re: Коровы (3 ответов, оставленных в Problems)
А по подробнее можете объяснить?
3 2010-02-28 17:05:46
Тема: Коровы (3 ответов, оставленных в Problems)
В селе Максоярославке коровы обычно пасутся на лужайках, соединенных дорожками, на каждой
лужайке пасется хотя бы одна корова. При этом для каждой пары лужаек есть ровно один способ
пройти от одной лужайки до другой. По каждой дорожке можно двигаться в обоих направлениях.
Главный фермер села хочет построить на лужайках два коровника для своих коров. Ясно, что
каждая корова вечером будет возвращаться именно в тот коровник, который ближе к ее лужайке (если
расстояние до коровников одинаково, то в любой из них). Поэтому возникает задача определения
такого расположения коровников, при котором наибольшее из расстояний, проходимых коровами, было
бы минимально.
Количество лужаек N <= 100000
4 2010-01-19 20:47:35
Re: Ломаная (2 ответов, оставленных в Problems)
Спасибо. Решил используя дерево отрезков с сжатием координат.
5 2010-01-19 20:41:05
Тема: Дремучий лес - 2 (4 ответов, оставленных в Problems)
Просека — эта такая прямая линия, которая проходит через лес (то есть деревья есть как с одной стороны от этой линии, так и с другой), и при этом она не проходит ни через одно из деревьев леса, а также не касается деревьев. Будем говорить, что лес является дремучим, если в нем нет ни одной просеки.
На плане леса все деревья изображаются кругами. Никакие два круга не пересекаются и не касаются друг друга. Требуется по этому плану определить, является ли лес дремучим.
N <= 200 (количество деревьев)
http://acmp.ru/index.asp?main=task&id_task=232
6 2010-01-17 17:36:00
Тема: Мэры (0 ответов, оставленных в Problems)
Во Флатландии имеется N городов, расположенных на плоскости в точках с координатами (xi, yi). Недавно президент Флатландии решил назначить в каждом городе мэра. При этом, чтобы его нельзя было уличить в дискриминации, он решил назначить на эти посты как мужчин, так и женщин. Для каждой горизонтальной и вертикальной прямой назовем несправедливостью модуль разности между количеством городов на этой прямой, в которых на пост мэра назначены мужчины и количеством городов на этой прямой, в которых на этот пост назначены женщины.
Чтобы показать свою беспристрастность, президент хочет минимизировать суммарную несправедливость по всем вертикальным и горизонтальным прямым. Для каждого города надо определить кого назначить мэром мужчину или женщину. Координаты всех городов целые и N <= 20000
7 2010-01-17 10:07:31
Тема: Ломаная (2 ответов, оставленных в Problems)
На плоскости дана ломаная, каждое из звеньев которой перпендикулярно биссектрисе одного из углов, образованных координатными осями. Никакая вершина ломаной не лежит на звене ломаной(кроме, возможно, того звена, концом которого она является). В частности, никакие две вершины ломаной не совпадают. Ваша задача — подсчитать число точек самопересечения ломаной.
n <= 100000 (количество вершин ломаной)
Подскажите как можно решить эту задачу?