Задачка

← →
Kerk © (2004-04-04 13:56) [0]

Как решать?

Доска с гвоздями. В доску шириной W вбито N гвоздей диаметром d. Монета диаметром D лежит на левой части доски. Можно ли передвинуть ее на правый край так, чтобы при передвижении монета все время оставалась полностью лежащей на доске? Входной файл содержит: в первой строке - значения W, N, d, D. в следующих N строках - координаты x,y вбитых гвоздей (начало координат в левом нижнем углу доски). Все данные суть неотрицательные целые числа, не превосходящие 10000, 1 <= N <= 1000. Выходной файл содержит слово YES или NO. Лимит времени - 4 секунды.

← →
Mihey © (2004-04-04 14:07) [1]

Posledovatelno proverit rasstojanija mezhdu vsemi parami i esjo krat4ajshee rasstojani kazdogo gvozdja do kraj doski i dlja kazdogo gvozdja zapisat v tom slu4aje esli moneta mezdu dvumja ne prohodit to mezdu kakim gvozdjom i rassmatrivajemim ne prohodit. Dalee, imeja massiv s danninmi, prosmatrivaem ego v poiske vertikalnih perekritij t.e. tsepo4ek monet.

← →
Mihey © (2004-04-04 14:07) [2]

← →
Kerk © (2004-04-05 11:36) [3]

А как определить, что прохождению монеты между двумя гвоздями не мешает третий гвоздь?

>А как определить, что прохождению монеты между двумя гвоздями не мешает третий гвоздь?

Или как определить что прохождению монеты между двумя гвоздями не мешает N-2 гвоздей? :-)

Задачка Найти похожие ветки