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

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

Восстановить пароль Регистрация
 
neske
1419 / 786 / 55
Регистрация: 26.03.2010
Сообщений: 2,694
18.11.2011, 21:57     задача. дом у дороги. #1
вечер добрый.
подскажите способ решения.

во вложении полное условие задачи, но я все же расскажу еще и вкратце.
дано n прямых, нужно найти точку, для которой максимум из расстояний от точки до прямых был минимален.
Миниатюры
задача. дом у дороги.  
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 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
1419 / 786 / 55
Регистрация: 26.03.2010
Сообщений: 2,694
19.11.2011, 14:16  [ТС]     задача. дом у дороги. #3
спасибо! попробую.
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9373 / 5423 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
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
1419 / 786 / 55
Регистрация: 26.03.2010
Сообщений: 2,694
20.11.2011, 12:12  [ТС]     задача. дом у дороги. #5
спасибо.

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

Текущее время: 21:07. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru