Решение задачи на Си

[kisha]

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

[Carbon]

#include <iostream.h>

int main()
{

int N;

double min_x,max_x,min_y,max_y,x,y;

cin>>N;

for (int i=0;i<N;i++)
{
    cin>>x>>y;
    if (!i)
    {
        min_x=max_x=x;
        min_y=max_y=y;
    }
    else
    {
        if (x>max_x)
            max_x=x;
        else
            if (x<min_x)
                min_x=x;
        if (y>max_y)
            max_y=y;
        else
            if (y<min_y)
                min_y=y;
    }
}

cout<<"("<<min_x<<";"<<min_y<<")\n"
      <<"("<<max_x<<";"<<max_y<<")\n";

cin.get();

return 0;

}

[kisha]

Carbon..я думаю что ни так просто она решаеться а если как нидь по углом расмотреть прямоугольник и он окажеться наименьшим? че тогда? как эт записать?

[kisha]

Сообщение от Carbon

#include <iostream.h>

int main()
{

int N;

double min_x,max_x,min_y,max_y,x,y;

cin>>N;

for (int i=0;i<N;i++)
{
    cin>>x>>y;
    if (!i)
    {
        min_x=max_x=x;
        min_y=max_y=y;
    }
    else
    {
        if (x>max_x)
            max_x=x;
        else
            if (x<min_x)
                min_x=x;
        if (y>max_y)
            max_y=y;
        else
            if (y<min_y)
                min_y=y;
    }
}

cout<<"("<<min_x<<";"<<min_y<<")\n"
      <<"("<<max_x<<";"<<max_y<<")\n";

cin.get();

return 0;

}

Carbon..я думаю что ни так просто она решаеться а если как нидь по углом расмотреть прямоугольник и он окажеться наименьшим? че тогда? как эт записать?

[Alek86]

в лоб:

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

тьфу, неправильно прочел условие.
тогда и правда нетривиальная...

[Куок]

Элементарно!!! Находишь максимальное расстояние между любой парой всех возможных точек. полученный отрезок - основа. рассчитываешь координаты середины отрезка - точка С. С - принимаешь за центр окружности с радиусом максимального расстояния от С до любой точки множества кроме концов отрезка(точка А). кроме того через центр отрезка проводишь перпендикуляр такой же длины как полученный отрезок. Откладываешь проекцию с А на перпендикуляр, разность икса между центром отрезка и т.к.А умноженная на 2 и есть меньшая сторона прямоугольника.

[Alek86]

жесть
kisha, если буш проверять, хоть скажи, правильно это или нет?

[PuzzleC]

http://forum.vingrad.ru/index.php?sh...dpost&p=312889
Посмотри может поможет

[kisha]

Сообщение от Куок

Элементарно!!! Находишь максимальное расстояние между любой парой всех возможных точек. полученный отрезок - основа. рассчитываешь координаты середины отрезка - точка С. С - принимаешь за центр окружности с радиусом максимального расстояния от С до любой точки множества кроме концов отрезка(точка А). кроме того через центр отрезка проводишь перпендикуляр такой же длины как полученный отрезок. Откладываешь проекцию с А на перпендикуляр, разность икса между центром отрезка и т.к.А умноженная на 2 и есть меньшая сторона прямоугольника.

жуть..вот этим всем ты меня напугал как эт все написать то? я не знаю чувствую себя профаном.. помоги если не сложно

[kisha]

Сообщение от Alek86

в лоб:

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

тьфу, неправильно прочел условие.
тогда и правда нетривиальная...

попробую конечно..только получиться ли у меня что нидь из этого?! ты сам не проверял?