Такая еще задача:

Цитата

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

Жду хотя бы подсказки.
Спасибо.

Ищешь минимальные и максимальные x и y координаты точек - это и будет твой прямоугольник...

p0s0l
Уже сделал сегодня.
Но всё равно спасибо.

NiJazz
Так выложи решение. Мало ли кому понадобится еще.

Цитата

Ищешь минимальные и максимальные x и y координаты точек - это и будет твой прямоугольник...

рискну предположить, что все не так просто
это будет решением только в том случае, если есть условие параллельности сторон прямоугольника осям координат
если же прямоугольник может быть ориентирован как угодно, то как минимум придется определиться со словом "наименьший", а то мне кажется, что для разных критериев будут разные результаты
(в случае со сторонами, параллельными осям координат, похоже, результат получается для всех более-менее разумных критериев: площадь, периметр, диагональ, ...)
в общем случае можно предложить что-нибудь в таком роде:
1. зафиксировать направление, которому будут параллельны/перпендикулярны стороны прямоугольника
2. решить задачу для фиксированных направлений (как было предложено)
таким образом перебрать всевозможные направления и выбрать наилучшее

Среда: Turbo C++ 3

Код

#include <iostream.h> #include <stdlib.h> #include <conio.h> void main() {   clrscr();   randomize();   unsigned short pcount = 0;   cout << "Введите количество точек на плоскости: ";   cin >> pcount;   cout << endl;   struct point   {      int x;      int y;   };   point* points = new point[pcount];   for (int i=0;i<pcount;i++)   {      points[i].x = rand()%50+5;      points[i].y = rand()%50+5;   }   int maxx = 0;   int maxy = 0;   int minx = 32767;   int miny = 32767;   for (i=0;i<pcount;i++)   {      if (maxx<points[i].x) maxx = points[i].x;      if (maxy<points[i].y) maxy = points[i].y;      if (minx>points[i].x) minx = points[i].x;      if (miny>points[i].y) miny = points[i].y;   }   cout << "Вершины минимального прямоугольника: ";   cout <<'('<<minx<<','<<miny<<"), ("<<minx<<','<<maxy<<"), ";   cout <<'('<<maxx<<','<<miny<<"), ("<<maxx<<','<<maxy<<")";   cin.get();   cin.get(); }

припоздал маленько...

Не хватает такого кода:

Код

for (i=0;i<pcount;i++) {   delete &points[i]; }

Но тогда выдаёт ошибку "NULL poiter assignment".
Возиться долго не стал, поэтому оставил всё как есть. Если подскажите, как грамотно сделать освобождение памяти, буду благодарен.
Добавлено @ 17:57
maxim1000
Мысли очень правильные. Придётся это делать, если препод потребует.

Мне кажется, что maxim1000 прав: решение не так очевидно.

Например, следующие 4-е точки:

(0,0),(4,6),(6,4),(10,10). Твое решение даст: (0,0) и (10,10) (еще две вершины: (10,0) и (0,10)). Но решением будет прямоугольник под углом 45 градусов к осям - примерно это (-1,1), (1,-1), (9,11) и (11,9).

Ну если не паралельно осям, тогда можно модернизировать так:
1) ищем центр всех точек (это середина между min и max)
2) ищем точку, которая находится всех дальше от центра
так мы выяснили угол поворота прямоугольника (alpha)
3) поворачиваем ось координат на угол alpha
(вернее тут будет создан второй массив точек с измененными координатами)
4) теперь применяем первоначальный алгоритм (через min и max) на второй массив
5) результат поворачиваем на угол -alpha

Это я объяснил чтобы понятнее было, но в деле лучше вместо 3-4-5 не создавать второй массив, а на ходу поворачивать каждую точку и проверять на min/max...

Попробовал на простых примерах - вроде действует правильно...

2NiJazz

А зачем каждую точку удаляешь то? Ты ж блок выделял! Блок и удаляй!

Цитата

Но тогда выдаёт ошибку "NULL poiter assignment".

delete[] points;

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

Цитата

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

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

Цитата(maxim1000 @ 26.4.2004, 18:15)

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

А я вот попробовал проделать то же самое и получил противоположный результат

Нарисовал равностононний треугольник со стороной a, зафиксировал его
Совместил одну из вершин объемлющего прямоугольника с вершиной треугольника

Остальные вершины прямоугольника стал двигать вокруг треугольника
так, чтобы они касались его сторон
И стал смотреть, какая при этом получится площадь
Оказалось, что вершины этого прямоугольника двигаются по дугам окружностей
с центрами в серединах сторон треугольника
Движется по одной из дуг до тех пор, пока их стороны не совместятся,
после чего начинает двигаться по другой дуге

Площадь я считал 2 часа и в результате получил, что она равна
(sqrt(3)/4 + 1/2*cos(gamma))*a^2, где -pi/6<=gamma<=pi/6

Здесь граничные значения gamma соответствуют положению, когда стороны совмещены
И видно, что минимум площади достигается при таких значениях
Может, конечно, и я где-то ошибся , но вроде бы хорошо все проверял...