алгоритм горизонта
Как я нахожу вершины прерывистой линии, которая окружает контур в этом изображении? 
Возможный вход для примера выше:
WIDTH HEIGHT POSITION 3 9 17 5 9 9 12 4 8 3 11 3 10 7 1 2 3 19
Таким образом для этого примера решение было бы
[(1, 0), (1, 7), (3, 7), (3, 11), (6, 11), (6, 7), (9, 7), (9, 9), (14, 9), (14, 4), (17, 4), (17, 9), (20, 9), (20, 3), (21, 3), (21, 0)]
3 ответа
http://online-judge.uva.es/ p / v1 / 105.html - это то место, где я первоначально увидел проблему
И у Algorithmist есть объяснение решения: http://www.algorithmist.com/index.php/UVa_105
Это довольно просто. Создайте массив, длина которого равна длине оси X, инициализируйте его значением 0. По мере считывания входных данных записывайте высоты в этот массив, если высота >= текущему значению в этом месте массива.
Затем просто перебирайте массив, и каждый раз, когда значение меняется, это будет вершина.
По существу:
int heights[SIZE] = {0};
int i, width, pos, height, prev = -1;
while (scanf("%d %d %d", &width, &height, &pos) == 3) {
for (i = 0; i < width; ++i) {
if (heights[pos+i] < height)
heights[pos+i] = height;
}
}
for (i = 0; i < SIZE; ++i) {
if (heights[i] != prev) {
printf("(%d,%d) ", i+1, heights[i]);
prev = heights[i];
}
}
printf("\n");
В наивном случае это не кажется очень сложным алгоритмом. Знаете ли вы, что размер входных данных станет большим / насколько большим?
Моя первая попытка: попробуйте двигаться слева направо. Сначала выберите блок с крайним левым краем, который существует на линии начала координат. Поднимитесь на его вершину. Найдите все блоки с левым краем между текущей точкой и верхней правой точкой текущего блока. Из этого набора выберите ближайший (но проверьте наличие крайних падежов, каламбур не предназначен). Если набор пуст, начните прокладывать себе путь вниз по правой стороне блока, ища другие блоки, которые вы можете перехватить.
По сути, это именно то, как вы проследите это своим глазом.
Вы можете сделать простую оптимизацию, сохраняя отсортированные списки, а затем ища списки, а не находя наборы и копаясь. Например, можно сохранить 4 отсортированных списка блоков, каждый из которых отсортирован по координатам x или y одной из сторон.
Если у вас много, много блоков, вы можете рассмотреть возможность использования мульти-размерная структура данных для дальнейшей организации информации.