IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

> Задача на графы, Очень срочно!
сообщение
Сообщение #1


Новичок
*

Группа: Пользователи
Сообщений: 49
Пол: Женский
Реальное имя: Натали

Репутация: -  1  +


Помогите пожалуйста!! Завтра сдавать, я в графах ни бум-бум...очень прошу!
23. На плоскости заданы 2n точек своими координатами. Найдите уравнение какой-либо прямой, делящей данное множество точек на два подмножества по n точек.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
 
 Ответить  Открыть новую тему 
Ответов
сообщение
Сообщение #2


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(klik1602 @ 3.03.2011 23:07) *
23. На плоскости заданы 2n точек своими координатами. Найдите уравнение какой-либо прямой, делящей данное множество точек на два подмножества по n точек.

Допустим, координаты точек содержатся в массиве/массивах.
1. Упорядочиваем этот/эти массив/массивы по возрастанию X.
2. Если xn <> xn+1, то искомое равнение есть x = (xn + xn+1) / 2;
3. Если xn = xn+1, то..
4. найти минимальный ненулевой угол, опирающийся на точки из данного множества (назовем его A);
5. произвести поворот системы координат на A/2 (вокруг произвольной точки).
6. Перейти к 1.

Решение, правда, не имеет особого отношения к графам.. И еще: пункты 4 и 5, возможно, можно заменить на что-то попроще, немного менее детерминированное - например, поворот на случайный угол до тех пор, пока не выполнится условие в п.2.


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

Сообщений в этой теме
klik1602   Задача на графы   4.03.2011 3:07
Krjuger   Условие не совсем понятно.А что если некоторые точ…   4.03.2011 3:56
klik1602   у меня только это условие и никаких пояснений( зад…   4.03.2011 4:28
Lapp   23. На плоскости заданы 2n точек своими координата…   4.03.2011 4:50
klik1602   ммм, попробую завтра утром сделать, если успею, но…   4.03.2011 5:15
Lapp   не понимаю как вот это реализовать Реализовать э…   4.03.2011 10:05
TarasBer   1. Нам надо найти прямую, которая не параллельная …   4.03.2011 13:57
klik1602   добрый вечер, снова возвращаюсь к этой программе, …   27.03.2011 1:26
Krjuger   a[i]a[j]-это 2 точки нашего исходного массива,прин…   27.03.2011 6:04
Lapp   Я думаю, что в условии должно быть требование, что…   27.03.2011 6:13
klik1602   Цитата Пусть её уравнение M*x+N*y+k=0. , я так пон…   27.03.2011 16:46
Krjuger   Не совсем,смотрите его тождества. Если к равно 0…   27.03.2011 17:19
klik1602   нашла на просторах интернета похожую задачу на мою…   27.03.2011 20:13
Krjuger   Вы можете взять и скопировать этот алгоритм суда,е…   27.03.2011 21:17
klik1602   Отсортировав координаты точек в порядке неубывания…   27.03.2011 23:29
Lapp   но уверенности в том что правильно нету, не соглас…   28.03.2011 11:29
klik1602   подскажите хотя бы в каком месте ошибка, чтобы ис…   28.03.2011 20:10
Krjuger   Ну чтобы проверить,правильно или нет,нарисуйте на …   28.03.2011 20:34
klik1602   вот код: program L15_23; const maxn=100; type ko…   28.03.2011 22:30


 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 18.10.2019 0:45
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name