Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.80/5: Рейтинг темы: голосов - 5, средняя оценка - 4.80
neske
1527 / 894 / 192
Регистрация: 26.03.2010
Сообщений: 3,074
#1

задача. дом у дороги.

18.11.2011, 21:57. Просмотров 979. Ответов 4
Метки нет (Все метки)

вечер добрый.
подскажите способ решения.

во вложении полное условие задачи, но я все же расскажу еще и вкратце.
дано n прямых, нужно найти точку, для которой максимум из расстояний от точки до прямых был минимален.
0
Миниатюры
задача. дом у дороги.  
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.11.2011, 21:57
Ответы с готовыми решениями:

Задача на рекурсию. Найти кратчайшее расстояние между городами i и j даже если между ними нет прямой дороги
Дана матрица размером NxN с расстояниями между городами при наличии прямой...

Задача "Города и дороги"
Здравствуйте! :) Решаю задачу, но моё решение не проходит на 100%, а всего...

Односторонние дороги
Здравствуйте.Помогите пожалуйста решить задачу. Найти длину самого длинного...

Рисование в консоли (дома и дороги)
Подскажите. Есть абстрактный класс в котором я динамически выделяю память под...

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

4
valeriikozlov
Эксперт С++
4683 / 2509 / 751
Регистрация: 18.08.2009
Сообщений: 4,550
19.11.2011, 08:34 #2
Дам частичный ответ на задачу.
Для наглядности прикрепляю рисунок:

Рассмотрим координаты всех отрезков по оси Y.
Нужно найти два отрезка, которые не имеют общих значений по Y и имеют самую большую разность по Y между ближайшими у них точками. На рисунке это отрезки AB и CD , точки соответственно B и C
Ответ по Y будет среднее арифметическое Y точек B и C.
Тоже самое по X
В других случаях (когда нет таких отрезков) нужно считать по другому.
0
Вложения
Тип файла: doc Doc4.doc (24.5 Кб, 30 просмотров)
neske
1527 / 894 / 192
Регистрация: 26.03.2010
Сообщений: 3,074
19.11.2011, 14:16  [ТС] #3
спасибо! попробую.
0
easybudda
Модератор
Эксперт CЭксперт С++
10051 / 5971 / 1491
Регистрация: 25.07.2009
Сообщений: 11,306
19.11.2011, 14:18 #4
neske, я бы так примерно делал: для начала нужна структура вроде
C
1
2
3
4
5
struct POINT {
    double x;
    double y;
    double max_distance;
};
соответственно массив таких структур по количеству точек.
Кроме того нужна структура для прямой с уравнением Ax + By + C = 0
C
1
2
3
4
5
struct LINE {
    double a;
    double b;
    double c;
};
ну и массив таких структур по количеству прямых.
Заполняем массив точек, max_distance можно устанавливать в 0.0, заполняем массив прямых, а дальше для каждой точки ищем расстояние до каждой прямой и сохраняем максимальное, учитывая, что
http://www.cyberforum.ru/cgi-bin/latex.cgi?distance\, =\, \left| \frac{{a}_{l}{x}_{p}+{b}_{l}{y}_{p}+{c}_{l}}{\sqrt{{{a}_{l}}^{2}+{{b}_{l}}^{2}}} \right|
ну и в заключении по массиву точек ищем ту, у которой max_distance имеет минимальное значение.
Как-то так...
1
neske
1527 / 894 / 192
Регистрация: 26.03.2010
Сообщений: 3,074
20.11.2011, 12:12  [ТС] #5
спасибо.

Добавлено через 14 часов 51 минуту
easybudda, на счет кол-ва точек. мы же должны рассмотреть все точки в области от x min до x max и аналогично с y? а находим мы их из точек, которые задают прямые.
0
20.11.2011, 12:12
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.11.2011, 12:12

Алгоритм удаления лишних клеток дороги на тайловой карте
Есть тайловая карта, на которой сгенерирована дорога. Бирюзовым и синим...

Укажите в конце дороги. На пути к подсчитать количество слов
Укажите в конце дороги. На пути к подсчитать количество слов

В системе двухсторонних дорог за проезд каждой дороги взимается некоторая пошлина.
В системе двухсторонних дорог за проезд каждой дороги взимается некоторая...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru