Задание по программированию: Транспортный справочник, часть S. Построение маршрута до организаций

Условие

В этой части вы научитесь строить маршрут до ближайшего парка! А именно, вам понадобится не только искать организации по набору условий, но и строить маршрут от некой остановки до ближайшей подходящей организации. Новая функциональность заключается в обработке нового запроса — RouteToCompany.

Новые данные

Ещё в предыдущей части в описании организации были предусмотрены географические координаты (address.coords) и расстояния до ближайших остановок (nearby_stops). Координаты понадобятся для отображения организации на карте маршрута, а информация про ближайшие остановки используется напрямую при построении маршрута.

В routing_settings добавляется новая настройка маршрутизации — скорость пешехода pedestrian_velocity, измеряемая в км/ч (вещественное число от 0,001 до 1000).

Изменения существующей функциональности

В связи с добавлением новых типов элементов маршрута, старые нуждаются в более понятных названиях:

• Bus (поездка на автобусе) переименовывается в RideBus;

• Wait (ожидание автобуса) переименовывается в WaitBus.

Новый запрос — RouteToCompany

Помимо стандратного ключа "id" и "type": "RouteToCompany", новый запрос содержит два ключа:

• "from" — название остановки, где начинается маршрут.

• "companies" — описание ограничений на организацию, до которой необходимо построить маршрут.

Ограничения на организацию — это словарь, который может содержать ключи names, urls, rubrics, phones. Их структура и семантика абсолютно аналогичны части R.

Такой маршрут устроен следующим образом:

1. Сначала обычный маршрут между двумя остановками, как в запросе Route, в котором чередуются ожидание автобуса (WaitBus) и поездка на нём (RideBus).

2. И дополнительный элемент — проход пешком от последней остановки предыдущей части маршрута до целевой организации (WalkToCompany). Скорость пешехода считается равной routing_settings.pedestrian_velocity км/ч. Проход до организации возможен лишь от одной из остановок, указанных в nearby_stops этой организации, и занимает время, соответствующее указанному расстоянию между организацией и остановкой.

Ответ на запрос RouteToCompany устроен точно так же, как ответ на запрос Route:

• В случае отсутствия маршрута (в том числе по причине отсутствия нужных организаций) выводится {"error_message": "not found"}.

• В ключе total_time содержится суммарное время в минутах.

• В ключе items содержится массив элементов маршрута.

• В ключе map содержится карта маршрута в формате SVG.

Последним элементом в массиве items должен быть элемент, соответствующий проходу до организации, со следующими параметрами:

• "type": "WalkToCompany";

• "time" — затраченное время (в минутах);

• "stop_name" — остановка, от которой нужно пройти;

• "company" — основное название компании (см. условие части R).

Сам маршрут должен быть наибыстрым маршрутом данной структуры от указанной остановки до организаций, удовлетворяющих заданным ограничениям. Если существует несколько подходящих маршрутов, выводите любой из них.

Отображение организации на карте маршрута

Схема маршрута до организации должна содержать эту организацию и линию к ней от остановки.

Общая карта (выводимая в ответ на запрос Map) и карты обычных машрутов (Route) остаются без изменений и организаций не содержат.

Новые настройки отрисовки

Добавляются новые настройки отрисовки:

Новые слои

Добавляются следующие слои:

• "company_lines" — линия от последней остановки маршрута до организации;

• "company_points" — круг, обозначающий организацию;

• "company_labels" — надпись с названием организации.

На общей схеме и схемах обычных маршрутов эти слои не содержат объектов.

В случае, когда маршрут не содержит элементов RideBus и WaitBus, слой stop_labels должен содержать название одной остановки — той, от которой проложен маршрут.

Слой company_lines

Содержит ломаную из двух вершин: от остановки до координаты компании (про координату компании на карте см. ниже).

Свойства:

• Цвет линии (stroke) — "black".

• Толщина линии (stroke-width) — company_line_width.

• Формы конца линии (stroke-linecap) и соединений (stroke-linejoin) — "round".

Слой company_points

Содержит круг, обозначающий организацию.

Свойства:

• Центр (cx и cy) — координата организации.

• Радиус (r) — company_radius.

• Цвет заливки (fill) — "black".

Слой company_labels

Содержит надпись с полным названием компании, отрисованную по координате компании ровно тем же способом, что и названия остановок.

Полное название компании составим следующим образом:

• Если компания не содержит рубрик, полное название равно основному названию.

• В противном случае это название первой рубрики, пробел и основное название. Например, компания с первой рубрикой "Парк" и основным названием "Дендрарий" получает полное название "Парк Дендрарий".

Вычисление координат компаний

По аналогии с остановками, для каждой компании необходимо по её географическим координатам определить координаты на карте. Это делается для всех организаций сразу (гарантируется, что в address.coords для каждой организации заданы координаты), несмотря на то, что на любой карте не может быть нарисовано более одной организации.

Обратите внимание, что в JSON, поступающем на вход программе make_base, координаты компаний задаются в виде строк (см. примеры). Это сделано для сохранения точности при автоматической конвертации в protobuf.

Алгоритм из части M модифицируется для одновременного размещения на карте остановок и организаций:

1. Организации считаются опорными точками, так что их географические координаты предварительно не модифицируются.

2. Долготы и широты остановок и компаний одновременно подвергаются сжатию координат. Соседями каждой организации (для целей определения маршрутных соседей среди долгот и широт) считаются остановки, от которых можно до неё дойти.

3. x- и y-координаты вычисляются по сжатым координатам одновременно для остановок и для организаций.

Пример 1

Вход программы make_base

Вход программы process_requests

Выход программы process_requests

Выход программы process_requests, маршрут 1

Выход программы process_requests, маршрут 2

Пример 2

Вход программы make_base

Вход программы process_requests

Выход программы process_requests

Выход программы process_requests, маршрут 1

Выход программы process_requests, маршрут 2

Выход программы process_requests, маршрут 3

Ограничения

1. В этой части количество компаний не превышает 1000.

2. Для каждой компании количество элементов в nearby_stops не превосходит 10.

3. Количество запросов к process_requests не превосходит 500.

4. Каждое название остановки NearbyStop.name — название существующей остановки из транспортного справочника.

5. Расстояние NearbyStop.meters — положительное число, не превосходящее 1000000.

6. Количество остановок и автобусов, а также количество остановок любого автобусного маршрута не превосходят 100.

7. Ограничения по времени: 1 с для make_base, 3 с для process_requests.

8. Общее ограничение по памяти — 512 МБ.

Задание T пока недоступно, но не думаю, что оно намного сложнее чем S, решения прошлых заданий доступны здесь
https://github.com/momsspaghettti/coursera-c-plus-plus-modern-development/tree/master/Black