Задача на графы, Очень срочно! |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
Задача на графы, Очень срочно! |
klik1602 |
Сообщение
#1
|
Новичок Группа: Пользователи Сообщений: 49 Пол: Женский Реальное имя: Натали Репутация: 1 |
Помогите пожалуйста!! Завтра сдавать, я в графах ни бум-бум...очень прошу!
23. На плоскости заданы 2n точек своими координатами. Найдите уравнение какой-либо прямой, делящей данное множество точек на два подмножества по n точек. |
TarasBer |
Сообщение
#2
|
Злостный любитель Группа: Пользователи Сообщений: 1 755 Пол: Мужской Репутация: 62 |
1. Нам надо найти прямую, которая не параллельная ни одной a[i]a[j].
2. Пусть её уравнение M*x+N*y+k=0. Сортируем массив чисел M*a[i].x + N*a[i].y + k (то есть для каждой точки берём такое число, потом сортируем массив таких чисел). Получили массив b[i]. Берём c := (b[n]+b[n+1])/2 - ну то есть число из середины массива. В качестве ответа берём M*x+N*y+(k-c): ведь у ровно половины точек число M*a[i].x + N*a[i].y + k-c будет строго положительно, а у другой половины - строго отрицательно. Вот по поводу пункта 1 что я думаю. Метод взятия случайной прямой вида a:=random*2*pi; cos(a)*x + sin(a)*y = 0; с высокой вероятностью быстро найдёт ответ, если он есть. А его может не быть. Если есть совпадающие точки, то мы уже обламываемся, всё резко усложняется. Детерминированный алгоритм придумать для такого случая я вообще не могу. Если все разные. Можно тупо перебрать, да (только не по тройкам точек, а по парам). Мне это не нравится. Можно взять минимальное ненулевое dx := a[i].x-a[j].x (для этого надо отсортировать координаты x и перебрать пары соседних). Взять максимальное dy := a[i].y-a[j].y (для этого надо вычесть максимум из минимума) Взять x*2*dy - y*dx = 0 в качестве искомой прямой: ведь вектор (dx; 2*dy) не параллелен ни одному отрезку a[i],a[j], потому что его тангенс наклона вдвое превышает все возможные тангенсы наклона отрезков, соединяющих точки из набора. правка: увеличил буквы в уравнении прямой, а то тавтология Сообщение отредактировано: TarasBer - -------------------- |
Текстовая версия | 26.04.2024 1:03 |