Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
neske
1502 / 869 / 84
Регистрация: 26.03.2010
Сообщений: 2,983
#1

задача. дом у дороги. - C++

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

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

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

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

Задача "Города и дороги" - C++
Здравствуйте! :) Решаю задачу, но моё решение не проходит на 100%, а всего лишь на 50%. Помогите-подскажите, что я делаю не так. ...

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

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

Симулятор работы железной дороги - C++
Всем привет, ребят. Сразу к делу: поставлена задача написать симулятор(работы железной дороги). Сразу решил юзать sfml(с целью отображение...

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

4
valeriikozlov
Эксперт С++
4670 / 2496 / 321
Регистрация: 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
1502 / 869 / 84
Регистрация: 26.03.2010
Сообщений: 2,983
19.11.2011, 14:16  [ТС] #3
спасибо! попробую.
0
easybudda
Модератор
Эксперт CЭксперт С++
9681 / 5631 / 954
Регистрация: 25.07.2009
Сообщений: 10,808
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
1502 / 869 / 84
Регистрация: 26.03.2010
Сообщений: 2,983
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
Привет! Вот еще темы с ответами:

Алгоритм удаления лишних клеток дороги на тайловой карте - C++
Есть тайловая карта, на которой сгенерирована дорога. Бирюзовым и синим обозначена дорога. Видно, что участок, обозначеный жёлтым...

В системе двухсторонних дорог за проезд каждой дороги взимается некоторая пошлина. - C++
В системе двухсторонних дорог за проезд каждой дороги взимается некоторая пошлина. Найти путь из города А в город Б с минимальной...

Определить можно ли закрыв какие-либо 3 дороги системы, добиться того, чтобы нельзы было попасть в город - C++
По системе двусторонних дорог, определить можно ли закрыв какие-либо 3 из них, добиться того, чтобы из города А нельзя было попасть в город...

Автоматически построить дороги из единиц между "городами" - C++
Подскажите как такое можно сделать: Нужно задать координаты точек (городов), значение которых в масиве -1, и их же вывело на экран и...


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

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

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