1 Тема от azizkhan Отредактировано azizkhan (2010-01-19 20:42:15)

  • azizkhan
  • Участник
  • Неактивен
  • Зарегистрирован: 2010-01-04
  • Сообщений: 7

Тема: Дремучий лес - 2

Просека — эта такая прямая линия, которая проходит через лес (то есть деревья есть как с одной стороны от этой линии, так и с другой), и при этом она не проходит ни через одно из деревьев леса, а также не касается деревьев. Будем говорить, что лес является дремучим, если в нем нет ни одной просеки.

На плане леса все деревья изображаются кругами. Никакие два круга не пересекаются и не касаются друг друга. Требуется по этому плану определить, является ли лес дремучим.
N <= 200 (количество деревьев)
http://acmp.ru/index.asp?main=task&id_task=232

2 Ответ от e-maxx

  • e-maxx
  • admin
  • Неактивен
  • Откуда: Саратов
  • Зарегистрирован: 2009-06-10
  • Сообщений: 360

Re: Дремучий лес - 2

Видимо, просто перебрать все возможные варианты просеки - это касательные к окружностям (требование не-касания деревьев легко избежать добавлением-отнятием EPS к координатам или например радиусам деревьев), и каждую такую касательную проверить.

Сайтe-maxx

  • Зарегистрирован: 2021-01-19
  • Сообщений: 1

Re: Дремучий лес - 2

azizkhan пишет:

Просека — эта такая прямая линия, которая проходит через лес (то есть деревья есть как с одной стороны от этой линии, так и с другой), и при этом она не проходит ни через одно из деревьев леса, а также не касается деревьев. Будем говорить, что лес является дремучим, если в нем нет ни одной просеки.

На плане леса все деревья изображаются кругами. Никакие два круга не пересекаются и не касаются друг друга. Требуется по этому плану определить, является ли лес дремучим.
N <= 200 (количество деревьев)
http://acmp.ru/index.asp?main=task&id_task=232


Добрый день!
Получилось ли у вас решить в свое время эту задачу?)
Если да, то можете поделиться, пожалуйста?

  • Зарегистрирован: 2020-04-23
  • Сообщений: 14

Re: Дремучий лес - 2

programmerrus пишет:
azizkhan пишет:

Просека — эта такая прямая линия, которая проходит через лес (то есть деревья есть как с одной стороны от этой линии, так и с другой), и при этом она не проходит ни через одно из деревьев леса, а также не касается деревьев. Будем говорить, что лес является дремучим, если в нем нет ни одной просеки.

На плане леса все деревья изображаются кругами. Никакие два круга не пересекаются и не касаются друг друга. Требуется по этому плану определить, является ли лес дремучим.
N <= 200 (количество деревьев)
http://acmp.ru/index.asp?main=task&id_task=232


Добрый день!
Получилось ли у вас решить в свое время эту задачу?)
Если да, то можете поделиться, пожалуйста?


Тоже интересует.

В качестве хобби модифицирую игры. Если кому интересно, можете скачать кс 1 6 со скинами кс го моего творения на пробу.

5 Ответ от AetiyShul

  • AetiyShul
  • AetiyShul
  • Участник
  • Неактивен
  • Откуда: Ссылку на клуб в профиле
  • Зарегистрирован: 2021-03-10
  • Сообщений: 2

Re: Дремучий лес - 2

действительно дремучий лес

СайтAetiyShul