Колличество точек 4<n<1000.
Каждая точка заданна парой чисел (x;y).
Провести через M точек выпуклый M-угольник внутри которого лежат все остальные точки заданные значением M<=n
Вывести на экран координаты вершины M.
Заранее спасибо!

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

T>Колличество точек 4<n<1000.
T>Каждая точка заданна парой чисел (x;y).
T>Провести через M точек выпуклый M-угольник внутри которого лежат все остальные точки заданные значением M<=n
T>Вывести на экран координаты вершины M.

Это называется "выпуклая оболочка" (convex hull).
Поиск в гугле, алголисте и RSDN тебе поможет.

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

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

T>>Колличество точек 4<n<1000.
T>>Каждая точка заданна парой чисел (x;y).
T>>Провести через M точек выпуклый M-угольник внутри которого лежат все остальные точки заданные значением M<=n
T>>Вывести на экран координаты вершины M.

К>Это называется "выпуклая оболочка" (convex hull).

Не совсем. В выпуклой оболочке может быть другое количество вершин C != M.
Легко придумать случай, когда решения нет.
А "наглядное пособие" по convex hull здесь.

Здравствуйте, Triniti,

Что же твой Neo тебе не помогает?

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

T>Колличество точек 4<n<1000.
T>Каждая точка заданна парой чисел (x;y).
T>Провести через M точек выпуклый M-угольник внутри которого лежат все остальные точки заданные значением M<=n
T>Вывести на экран координаты вершины M.
T>Заранее спасибо!

Данная задача в общем случае имеет бесконечное множество решений.

Здравствуйте, Murom, Вы писали:
M>Данная задача в общем случае имеет бесконечное множество решений.
Ну так продемонстирируйте пожалуйста хотябы одно из них. Очень срочно нужно!

Здравствуйте, Triniti, Вы писали:
Минимальный выпуклый многоугольник строим так:
1. Находим самую левую точку( т.е. с минимальной координатой Х ). Назовем эту точку О
2. Через O проводим луч проходящий через одну(назовем ее О_1 ) из точек так чтобы все прочие точки лежали "ниже" этого луча.
3. Через точку О_1 проводим луч аналогично пункту 2 и т.д.

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

T>>>Колличество точек 4<n<1000.
T>>>Каждая точка заданна парой чисел (x;y).
T>>>Провести через M точек выпуклый M-угольник внутри которого лежат все остальные точки заданные значением M<=n
T>>>Вывести на экран координаты вершины M.

К>>Это называется "выпуклая оболочка" (convex hull).

VC>Не совсем. В выпуклой оболочке может быть другое количество вершин C != M.

Секундочку. M — это количество точек выпуклого многоугольника. А общее количество точек — это N.
"все остальные точки заданные значением M<=n" я так понимаю, что речь идёт об отношении количеств, а не отношении порядковых номеров точек.

Так что M-угольник — это выпуклая оболочка множества N точек.

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

К>Секундочку. M — это количество точек выпуклого многоугольника. А общее количество точек — это N.
К>"все остальные точки заданные значением M<=n" я так понимаю, что речь идёт об отношении количеств, а не отношении порядковых номеров точек.

К>Так что M-угольник — это выпуклая оболочка множества N точек.

Я понял по-другому

Есть n точек на плоскости. 4 < n < 1000. И еще задано число M <= n.
Провести через M точек выпуклый M-угольник внутри которого лежат все остальные точки.

Я бы уточнил у преподавателя, что же имеется ввиду на самом деле.

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

VC>Я понял по-другому

VC>Есть n точек на плоскости. 4 < n < 1000. И еще задано число M <= n.
VC>Провести через M точек выпуклый M-угольник внутри которого лежат все остальные точки.

То есть, взять M каких-то точек из данного множества и провести M-угольник через них (т.е. эти точки лежат не в вершинах, а на сторонах)? Тогда действительно, бесконечное (континуальное) множество решений.

В любом случае, эти точки должны быть (некоторыми) вершинами выпуклой оболочки — иначе построить охватывающий многоугольник не получится.

В принципе, можно просто выбрать M разных направлений и найти за O(M*N) самые "крайние" по этим направлениям точки.
Например, самую левую, самую правую, самую верхнюю, самую нижнюю.
Но тут есть риск того, что одна и та же точка окажется и самой верхней, и самой левой...

Поэтому наиболее общее решение — это всё-таки
1) найти выпуклую оболочку, и пусть это будет C-угольник (C >= M)
2) найти M-угольник, в который этот C-угольник вписан.
Как именно это сделать — нужно подумать. Вертится одно решение, но пока что не формализуется.

VC>Я бы уточнил у преподавателя, что же имеется ввиду на самом деле.

Это лучшее, что можно посоветовать! +.

M>>Данная задача в общем случае имеет бесконечное множество решений.
T>Ну так продемонстирируйте пожалуйста хотябы одно из них. Очень срочно нужно!

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

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

T>Колличество точек 4<n<1000.
T>Каждая точка заданна парой чисел (x;y).
T>Провести через M точек выпуклый M-угольник внутри которого лежат все остальные точки заданные значением M<=n
T>Вывести на экран координаты вершины M.
T>Заранее спасибо!

еще один студент?..