Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/7: Рейтинг темы: голосов - 7, средняя оценка - 5.00
0 / 0 / 0
Регистрация: 23.01.2015
Сообщений: 13
1

Квадрат с вершинами из первого множества накрывает все точки второго множества и имеет минимальную площадь

07.02.2015, 17:09. Просмотров 1444. Ответов 7
Метки нет (Все метки)


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

помогите плиз!!! готов заплатить за решение...
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
07.02.2015, 17:09
Ответы с готовыми решениями:

Выбрать 4 точки множества так, чтобы квадрат с вершинами в этих точках накрывал все точки второго множества
Даны два множества точек на плоскости. Выбрать четыре различные точки первого множества так,...

В матрицу записать 1, если удвоенный элемент первого множества меньше элемента второго множества
Здравствуйте! Не могу понять, где ошибка в коде... Пользователь вводит размер первого множества,...

Определить, являются ли точки заданного множества вершинами параллелограмма
Здравствуйте! Такое вот задание: Определить, являются ли точки заданного множества вершинами...

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

__________________
Помогаю в написании студенческих работ здесь.
Записывайтесь на профессиональные курсы C++ разработчиков
7
897 / 418 / 159
Регистрация: 02.04.2014
Сообщений: 1,206
07.02.2015, 19:46 2
а точки как-то упорядочены? почему из первых точек должен получиться именно квадрат?

Приблизительно делал бы так: первым циклом проглядел все точки второго множества и определил "габариты" области: точка1 минимальные X,Y; точка2-(минимальный Х, макс_Y) ; точка3-(maxX,maxY); точка4-(maxX,minY)

Вторым циклом пройтись по точкам первого множества и найти 4 точки с такими же критериями, но удовлетворяющих условию близости к точкам второго множества.
0
1 / 1 / 0
Регистрация: 16.10.2014
Сообщений: 34
08.02.2015, 01:38 3
Уточни, пожалуйста, квадрат задается двумя точками(противоположные вершины) или 4 точками?

Добавлено через 1 час 36 минут
Короче, посмотри этот код, может он натолкнет тебя на умную мысль)) Здесь я определяю не квадрат, а четырёхугольник заданный двумя точками
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <iostream>
#include <vector>
 
using namespace std;
 
struct Point
{
double x;
double y;
 
friend istream & operator>> (istream &is,Point & P)
{
    is>>P.x>>P.y;
return is;
}
 
friend ostream & operator<< (ostream &os,Point & P)
{
    os<<"X: "<<P.x<<", Y: "<<P.y<<endl;
return os;
}
};
 
bool is_own_sq (Point *mas,int size,Point A,Point B);
 
vector< pair<Point,Point> > SqSet(Point* fs,int n,Point* ss,int m)
{   
     vector< pair<Point,Point> > res;
 
    for(int i(0);i<n;i++)
    {
        for(int j = i+1;j<n;j++)
        {
        if( is_own_sq(ss,m,fs[i],fs[j]) )
        {
            res.push_back( pair<Point,Point> ( fs[i],fs[j] ) ); 
        }
        }
    }
 
    return res;
}
 
 
bool is_own_sq (Point *mas,int size,Point A,Point B)
{
    bool res;
    for(int i(0);i<size; i++)
    {
        if (   (mas[i].x>A.x && mas[i].y<A.y &&mas[i].x<B.x && mas[i].y>B.y)  ||  (mas[i].x<A.x && mas[i].y>A.y &&mas[i].x>B.x && mas[i].y<B.y)   )
        {
            res = true;
        }
        else return false;
    }
 
    return res;
}
 
pair<Point,Point> Min_Sq(vector<pair<Point,Point> > vec)
{
    pair<Point,Point> min = *vec.begin();
 
    double S = abs( (min.second.x - min.first.x) * (min.first.y - min.second.y) );
    
    for(int i(0);i<vec.size();i++)
    {
        if(S < abs( ( (*vec.begin()).second.x - (*vec.begin()).first.x) * ((*vec.begin()).first.y - (*vec.begin()).second.y) ) )
        {
            min = vec.front();
        }
        else {vec.front();}
    }
    return min;
}
 
int main ()
{
    int n;
    int m;
 
    cout<<"Enter size of sets:\nfirst: "<<endl;
    cin>>n;
    cout<<"second: ";
    cin>>m;
    cout<<endl;
 
    Point* firstSet = new Point[n];
    Point *secondSet = new Point[m];
 
    for(int i(0);i<n;i++)
    {
        cout<<"Enter a first set:"<<endl;
        cin>>firstSet[i];
    }
    cout<<endl;
    for(int i(0);i<m;i++)
    {
        cout<<"Enter a second set:"<<endl;
        cin>>secondSet[i];
    }   
 
    vector< pair<Point,Point> > RESULT = SqSet(firstSet,n,secondSet,m);
 
    cout<<"Points, which are good:"<<endl;
    if (RESULT.size() == 0){cout<<"There is no points!\n";}
    else{
    for(int i(0);i<RESULT.size();i++)
    {
        cout<<RESULT.front().first <<RESULT.front().second <<endl;
    }
    pair<Point,Point> MIN = Min_Sq(RESULT);
    cout<<"Point with min sq: "<<endl<<MIN.first<<MIN.second;
    }
    system("pause");
    return 0;
}
Это работает, но крайне ненадежно. Так что желательно сделать решение более оптимальным, но у меня нет идей))
0
Заблокирован
08.02.2015, 09:34 4
Цитата Сообщение от Master_C Посмотреть сообщение
помогите плиз!!! готов заплатить за решение...
Могу перевести во фриланс.
Ваше решение?
0
0 / 0 / 0
Регистрация: 23.01.2015
Сообщений: 13
10.02.2015, 08:44  [ТС] 5
всем спасибо. сам справился)
0
1 / 1 / 0
Регистрация: 28.01.2014
Сообщений: 109
19.05.2015, 22:44 6
Master_C, как? не подскажете?
0
0 / 0 / 0
Регистрация: 24.11.2014
Сообщений: 3
11.01.2016, 15:44 7
Master_C , будьте так любезны, подскажите ваше решение, пожалуйста.А то уже неделю голову ломаю(
0
0 / 0 / 0
Регистрация: 23.01.2015
Сообщений: 13
12.01.2016, 10:13  [ТС] 8
эммм... попробуй найти решение, я даже не помню для чего мне это нужно было)
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
12.01.2016, 10:13

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь или здесь.

Массив: Выбрать три различные точки первого множества так, чтобы треугольник с вершинами в этих точках накрывал все точки второго множества
Здравствуйте. При реализации задачи я столкнулся с некоторой трудностью (ну, по крайней мере для...

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

Множества. Сформировать множества оценок, которые есть и у первого и второго, но нет у третьего ученика
Даны по 10-бальной шкале оценки по информатике трех учеников (три массива). Сформировать множества...

Определить найдутся среди точек заданного множества точки являющиеся вершинами правильной пирамиды
У меня такая тема попалась: Определить найдутся среди точек заданного множества точки являющиеся...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.