Привет всем.
Незнаю, может ктото ето уже слышал и решал.
Такая задача. Заданы координаты точек на плоскости. Количество точек кратно трем. Точек с одинаковыми координатами нет. Напишите програмку, которая будет рисовать треугольники с вершинами в заданых точках. Условие — треугольники не должны пересекаться и иметь общих вершин.

Здравствуйте, Аноним, Вы писали:

А>Привет всем.
А>Незнаю, может ктото ето уже слышал и решал.
А>Такая задача. Заданы координаты точек на плоскости. Количество точек кратно трем. Точек с одинаковыми координатами нет. Напишите програмку, которая будет рисовать треугольники с вершинами в заданых точках. Условие — треугольники не должны пересекаться и иметь общих вершин.

брутфорс: рассматриваем все варианты расположения треугольников и проделываем попарных сравнений треугольников на непересекаемость их сторон для каждого варианта

Здравствуйте, sadomovalex, Вы писали:

Да, от задачи не осталось и мокрого места. Есть доказательство, что проще нельзя?

Здравствуйте, deniok, Вы писали:

D>Здравствуйте, sadomovalex, Вы писали:

D>Да, от задачи не осталось и мокрого места. Есть доказательство, что проще нельзя?

нет конечно, это первая мысль

Здравствуйте, <Аноним>, Вы писали:

А>Привет всем.
А>Незнаю, может ктото ето уже слышал и решал.
А>Такая задача. Заданы координаты точек на плоскости. Количество точек кратно трем. Точек с одинаковыми координатами нет. Напишите програмку, которая будет рисовать треугольники с вершинами в заданых точках. Условие — треугольники не должны пересекаться и иметь общих вершин.

Может стоит добавить, что не найдется таких 3 точек, которые бы лежали на одной прямой?

Здравствуйте, tinytjan, Вы писали:

T>Может стоит добавить, что не найдется таких 3 точек, которые бы лежали на одной прямой?

Ну тогда совсем просто: сортируем по x, и берем по 3 подряд.

Здравствуйте, Иванков Дмитрий, Вы писали:

ИД>Здравствуйте, tinytjan, Вы писали:

T>>Может стоит добавить, что не найдется таких 3 точек, которые бы лежали на одной прямой?

ИД>Ну тогда совсем просто: сортируем по x, и берем по 3 подряд.

Хорошо, тогда если брать начальное условие, возникает такой вопрос:
если сторона одного треугольника содержит сторону или часть стороны другого -- такие треугольники считаются пересекающимися?

T>Хорошо, тогда если брать начальное условие, возникает такой вопрос:
T> если сторона одного треугольника содержит сторону или часть стороны другого -- такие треугольники считаются пересекающимися?

И еще один -- считаются ли треугольники с нулевыми углами? Т.е. вершины которых лежат на одной прямой.

Здравствуйте, Аноним, Вы писали:

А>Привет всем.
А>Незнаю, может ктото ето уже слышал и решал.
А>Такая задача. Заданы координаты точек на плоскости. Количество точек кратно трем. Точек с одинаковыми координатами нет. Напишите програмку, которая будет рисовать треугольники с вершинами в заданых точках. Условие — треугольники не должны пересекаться и иметь общих вершин.
И еще одно условие, чтобы исключить вариант решения "взять крайние 3, построить треугольник, и т.д.": периметр треугольников должен быть как можно меньшим (не обязательно строго минимальным из всех возможных вариантов, ...а может оно так в результате получается ).
(p.s. я ету задачу запостил).

По поводу возникающих вопросов еще условия — кол-во точек лежащих на одной прямой не ограничено, 3 точки одного результирующего треугольника могут лежать на одной прямой, т.е. нулевые углы допустимы.

Здравствуйте, Sash_net, Вы писали:

S_>По поводу возникающих вопросов еще условия — кол-во точек лежащих на одной прямой не ограничено, 3 точки одного результирующего треугольника могут лежать на одной прямой, т.е. нулевые углы допустимы.

1.строим вектора из начала координат к точкам.
2.выбираем 3 вектора минимальных (эти 3 точки будут вершинами треугольника).
3.отбрасываем эти точки.
делаем пока множество точек не пустое

Здравствуйте, ERROR_ALREADY_EXISTS, Вы писали:

ERR>Здравствуйте, Sash_net, Вы писали:

S_>>По поводу возникающих вопросов еще условия — кол-во точек лежащих на одной прямой не ограничено, 3 точки одного результирующего треугольника могут лежать на одной прямой, т.е. нулевые углы допустимы.

ERR>1.строим вектора из начала координат к точкам.
ERR>2.выбираем 3 вектора минимальных (эти 3 точки будут вершинами треугольника).
ERR>3.отбрасываем эти точки.
ERR>делаем пока множество точек не пустое

Вродебы вариант, но в етом случае периметр врятли будет близок к минимальному, можно решить по другому. И вродебы треугольники при такой сортировке могут пересекаться:

|
|
| o
|o
|
|* *
|
|___*___o_______

Здравствуйте, Sash_net, Вы писали:

S_> нулевые углы допустимы.

И-и-и, какой хитрый дядя! Мы тут думаем, мучаемся, а нам бац

То есть есть ситуации (скажем все точки на одной прямой, есть ли ещё?) когда без нулевых углов неразрешимо. Но если разрешимо — почему бы не поискать?

Здравствуйте, deniok, Вы писали:

D>есть ли ещё?

есть, конечно, когда много на прямой и одна в стороне, ну и т.д.

Здравствуйте, Sash_net, Вы писали:

S_>По поводу возникающих вопросов еще условия — кол-во точек лежащих на одной прямой не ограничено,

Задача становится интереснее...

S_>3 точки одного результирующего треугольника могут лежать на одной прямой, т.е. нулевые углы допустимы.

... и тут же становится опять скучнее.

Сортируем по x, в пределах одинаковых x сортируем по y. И берём по три подряд.

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, Sash_net, Вы писали:

S_>>По поводу возникающих вопросов еще условия — кол-во точек лежащих на одной прямой не ограничено,

К>Задача становится интереснее...

S_>>3 точки одного результирующего треугольника могут лежать на одной прямой, т.е. нулевые углы допустимы.

К>... и тут же становится опять скучнее.

К>Сортируем по x, в пределах одинаковых x сортируем по y. И берём по три подряд.

Берем по 3 подряд — самое простое решение, но можно красивее, с условием "периметр близкий к минимальному", кстати никакой геометрией (типа вычислять расстояния от центра коорд, между точками, строить векторы, считать углы, проверять не на одной ли прямой ...) при решении вообще заниматься не надо, ето задача чисто на программирование, необычная сортировка. Ето была лабораторка у меня на 3м курсе, на второй день написал прогу.

Здравствуйте, Аноним, Вы писали:

А>Привет всем.
А>Незнаю, может ктото ето уже слышал и решал.
А>Такая задача. Заданы координаты точек на плоскости. Количество точек кратно трем. Точек с одинаковыми координатами нет. Напишите програмку, которая будет рисовать треугольники с вершинами в заданых точках. Условие — треугольники не должны пересекаться и иметь общих вершин.

Задача решается так:
Нужно написать рекурсивную функцию, которой передается группа точек, функция должна разделить группу-свой аргумент на 2 группы с примерно (+/- 3) равным количеством точек по заданому направлению (по горизонтали либо вертикали), так, чтобы все точки, которые левее и правее (выше или ниже) некоторой координаты попали в разные группы. Далее ф-ция вызывает саму себя для каждой из двух полученных групп, причем в каждый следующий раз сортировка делается по другому направлению (если первый раз — по вертикали — второй по горизонтали и т.д.). Если в группе остается только 3 точки — нарисовать треугольник и выйти из функции.

Здравствуйте, Аноним, Вы писали:

А>Задача решается так:
А>Нужно написать рекурсивную функцию, которой передается группа точек, функция должна разделить группу-свой аргумент на 2 группы с примерно (+/- 3) равным количеством точек по заданому направлению (по горизонтали либо вертикали), так, чтобы все точки, которые левее и правее (выше или ниже) некоторой координаты попали в разные группы. Далее ф-ция вызывает саму себя для каждой из двух полученных групп, причем в каждый следующий раз сортировка делается по другому направлению (если первый раз — по вертикали — второй по горизонтали и т.д.). Если в группе остается только 3 точки — нарисовать треугольник и выйти из функции.

Ты какую задачу решаешь?

Если с допустимыми нулевыми углами треугольников, то решение (тривиальное) уже озвучено — сортируешь лексикографически пары (x,y) и строишь треугольники по получившемуся.

Площади твой подход тоже не минимализирует

   *                                *
      *
__________________________________________
     *                             *  
                                 *

А с ненулевыми углами — где гарантия, что три точки на выделенном в твоём алгоритме шаге не лежат на одной прямой?

Здравствуйте, deniok, Вы писали:
D>Если с допустимыми нулевыми углами треугольников, то решение (тривиальное) уже озвучено — сортируешь лексикографически пары (x,y) и строишь треугольники по получившемуся.

D>Площади твой подход тоже не минимализирует

Потому я писал не строго минимальный периметр, а "примерно минимальный", значительно меньший,чем при сортировке точек в один проход по одной координате или путем выбора по 3 точки которые лежат ближе всего к чему либо. Хотя в приведенном тобой примере эти периметры одинаковы.

Строго минимальный периметр думаю можно получить так — рекурсивная функция на последнем шаге, когда осталось 3 точки, возвращает перимерт полученного треугольника, не отображая его. если в группе более 3 точек, сортировка на 2 группы (вызов етой же ф-ции) запускается 2 раза — с сортировкой по X и по Y, подсчитывая для каждого вызова периметр построенных треугольников. Тот вызов, где периметр меньше, используется еще раз для результирующей сортировки точек и соотв периметр возвращается функцией. Вместо периметра также можно считать площадь. Помоему должно работать.

D>

D>   *                                *
D>      *
D>__________________________________________
D>     *                             *  
D>                                 *

D>

D>А с ненулевыми углами — где гарантия, что три точки на выделенном в твоём алгоритме шаге не лежат на одной прямой?

Я писал что треугольники с нулевыми углами допустимы, как решить задачу с условием отсутствия нулевых углов я наверно незнаю, но тоже можна придумать.