Великая Флатландская Стена

В один прекрасный день мне в руки попала задачка с какой-то там олимпиады. И она поставила меня в тупик! Предлагаю её вашему вниманию:

Имя входного файла:                                   input.txt
Имя выходного файла:                                 output.txt
Максимальное время работы на одном тесте: 10 секунд
Чтобы защитиь свою страну от набегов кочевников, призедент Флатландии решил построить Великую Флатландскую Стену. Страна Флатландия представляет собой координатную плоскость, её столица находится в точке (0, 0). Именно из столицы планируется начать строительство стены.
План постройки стены представляет собой последовательность инструкций строителям. Инструкции бывают следующего вида:
<направление строительства> <длина>
<направление перемещения> <расстояние>
В первом случае строители возводят стену указанной длины от точки, где они находятся, в указанном направлении. Во втором случае строители перемещаются на указанное расстояние в указанном направлении, не возводя при этом стены.
Направление строительства задается заглавной латинской буквой, а напраление перемещения - строчной латинской буквой. Соответствие букв направлениям приведено ниже:
Буква--------Направление------Вектор
N n               Север                 (0, 1)
E e               Восток                (1, 0)
S s               Юг                      (0, -1)
W w             Запад                  (-1, 0)
---------------------------------------
Длина и перемещение задаются в километрах и представляют собой целые числа.
Однако оказалось, что план министра может оказаться невыполнимым - в некоторый момент строители при выполнении инструкции могут столкнуться с уже построенной ими стеной! Выясните, выполним ли план министра и если нет, выведите координаты точки, в которой впервые произойдет столкновение с уже построенной стеной.
Формат входных данных.
На первой строке входного файла расположено число N - количество инструкций в плане министра (0 <= N <= 1000). Последующие N строк содержат инструкции плана. Их формат следующий: сначала идет одна из допустимых букв, заглавная буква означает, что следует строить стену, а строчная - что следует просто переместиться. Затем, отделенное от буквы ровно одним пробелом, идет целое число Хi - какой длины следует строить стену, либо на сколько надо переместиться (1 <= Xi <= (10 в 6-ой)).
Формат выходных данных.
На первой строке выходного файла выведите "yes", если план можно выполнить, либо "no", если нельзя. План можно выполнить, если строители, которых будем считать материальной точкой, никогда не оказываются в точке, через которую проходи участок стены, который они сейчас строят или только что построили (считаем стену состоящей из отрезков). В случае отрицательного ответа выведите на второй стоке координаты точки, в которой произойдет столкновение со стеной, сначала X, а затем Y. Числа должны быть разделены пробелом.
Примеры.
---input.txt----
4
N 4
e 3
S 2
w 1
---output.txt---
yes

---input.txt----
4
N 4
e 3
S 2
w 3
---output.txt---
no
0 2

P.S. Код в стиле ANSI/ISO безо всякого выпендрежа.

Сообщение отредактировано: vot - 07.11.02, 18:31

Ну и напиши интерпретатор этого языка - в чём проблема?  ??? ??? ???
Язык простой - фактически два оператора.
Создай в памяти Флатландию и вперёд - выполняй план министра!  ;)

проблема как раз в условии о времени работы. Несложно проводить простую проверку на пересечение стен - но неизвестно, какая производительность у тестового компа. А если это 386 то при N=1000 может произойти затык. Скорость перебора должна быть минимум 100000 пар стен в секунду - или придумывать другой алгоритм.

КАКОГО ПЕРЕБОРА? Ты просто строишь стену и смотришь - упёрлась она или нет. Какой тут нужен перебор - план-то у министра УЖЕ ЕСТЬ! Тебе не предлагают придумывать его самому.
Ну, читай весь файл целиком - мало ли какие могут быть ускорения.
А скорость машины была в условиях - только не в тексте, а перед глазами - какие были машины на олимпиаде, для таких и надо.

Судя по всему затык случился с алгоритмом определения пересечения 2 отрезков. (этот алгоритм рассматривают в курсе алгебра и начало анализа любого ВУЗа) Определяется с помощью уравнения прямой. Для любителей изврата, можно перевести в полярные координаты, и определить пересечения прямых, если это делать взяв в качестве начала отсчета точку одной прямой, а затем, другой, то можно установить пересечение отрезков.(сам пользовался этим алгоритмом, ну не помню я первого давно это было, на первом курсе). Так вот для решения данной задачи надо перебрать около 500000 пар отрезков(1-2,3-1 3-2,4-1 4-2 4-3...) На 800 пне я даже глазом моргнуть не успел, 10млн. переборов ЗАГРУЗИЛИ комп на 2 сек. Если пользоваться первым алгоритмом(для тех кто помнит) скорость расчетов будет раза в 3-4 выше.

Боже мой, что творится!
Какой пересечение прямых? Какие уравнения? Какие полярные координаты?
А что - просто посмотреть - есть ли перед тобой стена или нет - так нельзя?

Цитата Faust, 28.10.02, 07:31:11

Боже мой, что творится!
А что - просто посмотреть - есть ли перед тобой стена или нет - так нельзя?

а как смотреть? Это в реале достаточно глянуть (некоторым) и станет ясно, есть стена или нет.
Тут длина стены может достигать 10^6 единиц - создать матрицу и помечать в ней клеточки, через которые стена идёт памяти не хватит. Единственный приемлимый вариант - смотреть, не пересеклась ли новая стена с одной из построенных раньше. А это только через пересечение прямых.

P.S. Если я не прав и есть более быстрый способ - плиз, идею в студию.

Кстати, в общем случае запоминать места, где прошла стена, конечно, нельзя. ИМХО, такое решение достаточно топорно, и:
1) Памяти действительно может нехватить;
2) Алгоритм получается по крайнер мере двухпроходным, что не есть хорошо.
Вообще задачка мне напоминает задачку отсечения невидимых линий и поверхностей. А в этой области есть один замечательный алгоритм - называется алгоритм плавающих горизонтов. Обычно их берется два - для максимума и минимума по z-координате. В данном случае их должно быть 4. Т. е. фактически хранится внешний контур стены (что суть многоугольник), а каждая следующая прямая проверятся на пересечение с ним.

Цитата Flex_Ferrum, 28.10.02, 15:20:19

Т. е. фактически хранится внешний контур стены (что суть многоугольник), а каждая следующая прямая проверятся на пересечение с ним.

а если стена идёт двойной спиралью? сначала скручивается к центру, потом раскручивается наружу? Такой способ не пройдёт.

На самом деле, подойдет. С некоторой модификацией.

Кхе-кхе. Как оказалось, все гениальное просто.

Четыре массива, показывающих координаты нарисованных линий
begin_x[1000]
end_x[1000]
begin_y[1000]
end_y[1000]
+ переменная, показывающая, сколько нарисовано линий
Если строители находятся по X меньше конца(end_x) и больше начала(begin_x),
то если строители находятся по Y меньше конца(end_y) и больше начала(begin_y),
то точка найдена!
По моему вполне реально.

Ну не хотите хранить 1E9 точек карты Флатландии - разбейте её на области. По ходу строительства нумеруйте отрезки стены, а в описание области добавляйте факт - "через облать проходит стена №S". Тогда проверять очередную стену нужно будет не со всеми отрезками, а только с теми, которые проходят через данную область.

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

По ходу, суть задачи в том, что строится список занятых точек пространства и нужно выяснить - занята ли уже данная точка или нет. Не циклитесь на отрезках - они не имеют значения.

мама моя. вы все извраты! =)

а ведь я знаааааааю эту задачу )
и, между прочим, она была на городском туре олимпиады по программированию для _11-х_ классов (или для 10-х). как раз я её делал
и комп, на котором тестили прогу - целерон 400 =)))))
так что никаких наворотов в решении тут не нужно

я, помню, когда решал эту задачу, случайно подвесил свой комп. ну и решил подвесить ихний - не вышло так обидно было...
на самом деле задача несложная, но есть одно но - она должна работать на тестах с большим N, и если хранить координаты всех точек, занятых под стены, реально не хватает памяти!

я её решал так, как, по-моему, уже было предложено выше -
сделал массив из структур, где хранились координаты концов отрезков, образующих стены. а далее, когда ставится новая стена, проверял, не пересеклась ли она с одним из существующих. не помню точно, как я это делал. вродебы так -
если строим стену из n блоков и на север, то проверял, лежат ли точки x,y+i (0<=i<=n) на отрезках, которые записаны в массиве =)

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