Еще задачка, которая меня достала!:)

[Зиалот]

Люди подскажите, как решать задачку:
Короче дано множество точек с координатами(х,у)(могут быть вещественые).Нужно найти ур-е прямой такое, что бы по разные стороны от нее, было одинаковое кол-во точек.
Ну хотя бы суть=алгоритм.
Хелп

[Noname]

элементарно. Так как дополнительных условий нет, выбираем уравнение типа y=a. Это прямая, пересекающая ось ОУ в точке с координатой а. Теперь ищем эту самую величину а. Перебираем ее от минимальной координаты точки У к максимальной. Считаем количество точек, у которых координаты больше а и меньше а. Когда они сравняются, вот и ответ.
Может быть засада - несколько точек лежат на одной прямой с искомой координатой. Тогда пробуем уравнение х=а. Если и здесь нас постигает облом, думать надо тогда придется искать уравнение у=kх+b. В качестве одной из точек, через которую будем проводить прямую, можно взять ноль. Тогда y=kx. Для каждой точки считать, "выше" она или "ниже" прямой.
Тут может быть засада - несколько точек с пропорциональными координатами будут лежать на этой прямой.
Короче, самое общее решение пока предложить не могу. Но вариантов я тебе ужа накидал прилично - думай

[LittelBigFace]

1 что нужно сделать это узнать четное ли число точек или нет. Если число точек не четное тогда нужно чтобы прямая проходила через одну точку.
Затем берем упорядочеваем все координаты точек по отношению к X (слево минимыльный x с права максимальный). теперь найти середину отрезка я думаю не составить труда. Теперь другой момент если координаты x у 2х точек совпадают то тогда прямая сторится особым методом.
Выберем любую точку лежащую между 2 этими точками. У выбраной точки должна быть такая же координата x. Через нее пройдет прямамя.
Выбераем максимальную по y точку с одной стороны и минимальную с другой. Сравниваем ее по модулю. и соотвество прямая должна лежать либо выше если y больше у точки с права и ниже если y больше у точки слева. Затем выбераем нужную точку по принцепу описаного чуть выше. либо выше точки лежащей слева либо ниже точки лежащей справа (ксттаи выбор можно поменять тоесть все наоборот). И существует уравнение прямой где испотльзуются координаты 2х точек проходящих через эту прямую.

[LSL]

Зиалот мне нужны такие люди.

[Зиалот]

(LSL А зачем?я врятли смогу написать искусственный интелект..
LittelBigFace Noname Спаисбо товарисчи.
Но мне все-таки слабо понятно как быть с точностью..

[LSL]

Зиалот
А зачем?
Чтобы делать великие вещи!
Ты по ходу дела хорошо соображаешь в алгоритмах, если это не так, не важно. Главное одно, - желание ! Желание понять всё..взять недостигнутые вершины..мне нужны начинающие энтузиасты !


На счёт ИИ там всё проще чем ты думаешь, я объясню чуть попозже....

[Зиалот]

LSL А ты где работаешь?..и для чего тебе такие люди?

[LSL]

Зиалот Я студент второкурсник... бестолковый лентяй. Люблю жареную картошку.

и для чего тебе такие люди?
Будем свой Майкрософт делать

[Зиалот]

И как мы его будем делать..с чего начать-то? нажна четкая определенная цель. но я ее не знаю.

[LSL]

Зиалот
Цель: Создание AI для игры "Многоточие 2"
Результат: Собственный рост в своих глазах. Первая полноценная игра, которую можно будет распространять по интернету.

Продолжем тут:
http://www.u-antona.vrn.ru/forum/sho...threadid=12871

[Bais]

Меня тоже интересует вопрос AI
Мы с другом сейчас занимаемся чем-то подобным
Ничего конкретного еще не получилось, но идёт работа в этом направлении(создании ИИ); в основном поиск и прочтение большого колличества книг на тему, но также уже набросана структура классов и начинается реализация

[LSL]

Bais Интересно, на чём пишите ? Для себя ?

У меня задача в игре проще.

[Bais]

"Пишем"(это громко сказано) на C++ в среде VS.NET 7.1, пишем из каких-то своих соображений.

Кстати о точках: каким методом ведётся поиск лучшего хода ? (альфа-бетта или что-то иное ?)

[LSL]

Bais
пишем из каких-то своих соображений.
((:

Кстати о точках: каким методом ведётся поиск лучшего хода ? (альфа-бетта или что-то иное ?)

Что значит альфа бетта ? Поиск наилучшего хода никак не ведётся, алгоритм пока никто не писал, я думаю он должен состоять из двух частей:
http://www.u-antona.vrn.ru/forum/sho...threadid=12871