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

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

Войти
Регистрация
Восстановить пароль
 
neske
1466 / 833 / 69
Регистрация: 26.03.2010
Сообщений: 2,839
#1

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

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

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

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

C++ В системе двухсторонних дорог за проезд каждой дороги взимается некоторая пошлина.
C++ По системе двусторонних дорог определить, можно ли, закрыв какие-нибудь три дороги, добиться того, чтобы из города A нельзя было попасть в город B
C++ Рисование в консоли (дома и дороги)
Симулятор работы железной дороги C++
C++ Школа и дом Петра находятся на одной стороне улицы, надо узнать их номера.
C++ Задача "Города и дороги"
C++ Как можно осуществить замену слова в строке? (например, дом на мир и обратно)
Автоматически построить дороги из единиц между "городами" C++
Построить дороги из единиц между городами из "-1" C++
Укажите в конце дороги. На пути к подсчитать количество слов C++
C++ Алгоритм удаления лишних клеток дороги на тайловой карте
Электронная система «Доставка продуктов на дом» на С++ C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
4663 / 2489 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
19.11.2011, 08:34     задача. дом у дороги. #2
Дам частичный ответ на задачу.
Для наглядности прикрепляю рисунок:

Рассмотрим координаты всех отрезков по оси Y.
Нужно найти два отрезка, которые не имеют общих значений по Y и имеют самую большую разность по Y между ближайшими у них точками. На рисунке это отрезки AB и CD , точки соответственно B и C
Ответ по Y будет среднее арифметическое Y точек B и C.
Тоже самое по X
В других случаях (когда нет таких отрезков) нужно считать по другому.
Вложения
Тип файла: doc Doc4.doc (24.5 Кб, 29 просмотров)
neske
1466 / 833 / 69
Регистрация: 26.03.2010
Сообщений: 2,839
19.11.2011, 14:16  [ТС]     задача. дом у дороги. #3
спасибо! попробую.
easybudda
Эксперт С++
9453 / 5466 / 926
Регистрация: 25.07.2009
Сообщений: 10,490
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 имеет минимальное значение.
Как-то так...
neske
1466 / 833 / 69
Регистрация: 26.03.2010
Сообщений: 2,839
20.11.2011, 12:12  [ТС]     задача. дом у дороги. #5
спасибо.

Добавлено через 14 часов 51 минуту
easybudda, на счет кол-ва точек. мы же должны рассмотреть все точки в области от x min до x max и аналогично с y? а находим мы их из точек, которые задают прямые.
Yandex
Объявления
20.11.2011, 12:12     задача. дом у дороги.
Ответ Создать тему
Опции темы

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