Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 11.01.2017, 12:00   #1
Kef1r
Форумчанин
 
Регистрация: 13.05.2016
Сообщений: 111
По умолчанию Написать программу, которая определяет вершины квадрата содержащего макс. число заданных точек

На двумерной плоскости задано N точек с координатами (X1,Y1), (X2,Y2), ..., (Xn,Yn). Написать программу, которая из этих точек выделяет вершины квадрата, содержащего максимальное число заданных точек. Точки, расположенные на сторонах квадрата, принадлежат ему.
Вот что я смог сделать:
Код:
#include <iostream> 
#include <clocale>  
#include <conio.h>  
 
using namespace std;
bool IsPointInSquare(double x, double y)
{
 
if((x>=0 && x<=10)&&(y>=0 && y<=10))
 
return true;
 
else
return false;
 
}
 
 
int main()
{
 
setlocale( LC_CTYPE,"Russian" ); 
 
int n,k;
k=0;
double x, y;
cout<<" Сколько будет точек? ";
cin>>n;
for(int i=0;i<n;i++){
cout<<" Введите координату x : ";
cin>>x;
cout<<" Введите координату y : ";
cin>> y;
 
if(IsPointInSquare(x,y))
k++;
else
k=k+0;
}
 
cout << " Точек входящих в квадрат:  " << k << endl;
 
_getch();
return 0;
}
Здесь размеры квадрата заданы, а мне нужно чтобы после того как я задал точки программа проверяла, можно ли из этих точек сделать квадрат и если можно то посчитать количество точек, входящих в этот квадрат. Именно это не могу сам сделать. Хелп.
Kef1r вне форума Ответить с цитированием
Старый 11.01.2017, 14:04   #2
waleri
Старожил
 
Регистрация: 13.07.2012
Сообщений: 6,493
По умолчанию

Надо все точки сохранить в массив, потом создавать прямоугольники из всех комбинаций, проверить какие из прямоугольников являются квадратами и наконец подсчитывать сколкоь точек попадают в квадрат и запоминать результат.
waleri вне форума Ответить с цитированием
Старый 11.01.2017, 14:25   #3
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

Kef1r, а чем Вас ваша предыдущая тема не устроила?
Serge_Bliznykov вне форума Ответить с цитированием
Старый 11.01.2017, 15:29   #4
Kef1r
Форумчанин
 
Регистрация: 13.05.2016
Сообщений: 111
По умолчанию

Цитата:
Сообщение от Serge_Bliznykov Посмотреть сообщение
Kef1r, а чем Вас ваша предыдущая тема не устроила?
тем, что задача не решена, а тема замолкла. Я не знаю как реализовать проверку, образуют ли заданные точки квадрат.
Kef1r вне форума Ответить с цитированием
Старый 11.01.2017, 15:52   #5
ura_111
Участник клуба
 
Регистрация: 14.05.2016
Сообщений: 1,793
По умолчанию

Так что ты уже сделал?
ura_111 вне форума Ответить с цитированием
Старый 11.01.2017, 16:00   #6
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

Цитата:
Сообщение от Kef1r Посмотреть сообщение
Я не знаю как реализовать проверку, образуют ли заданные точки квадрат.
если задача найти любой квадрат (универсально, т.е. стороны квадрата не обязательно параллельны осям координат),
то можно брать 4-ре точки, искать расстояния между ними и сравнивать.

посмотрите вот здесь - Ответы Mail.Ru_ Образуют ли 4 точки квадрат_
или на форуме Точки на плоскости, нахождение квадрата

идея простая до безобразия.
берём точку A и находим расстояния от неё до 3-х других (B C D).
если две длины равны (стороны AB и AD) , а третья больше (диагональ AC), то тогда проверяем расстояние между этими двумя вершинами (вторая диагональ DB) и две другие стороны (BC и DC).
если стороны равны между собой и диагонали равны - то это квадрат.

p.s. расстояние находить легко по теореме Пифагора (как корень квадратный из суммы квадратов разностей соответствующих координат).

____________________________

Внимание! Важно! При сравнении вещественных величин (это дробные числа, с плавающий запятой) нельзя использовать прямое равенство!
вместо это используйте проверку на близость: вместо
Код:
if (Len1 == Len2)
пишите что-то вроде
Код:
if ( Math.Abs(Len1 - Len2 )<0.001)

Последний раз редактировалось Serge_Bliznykov; 11.01.2017 в 16:03.
Serge_Bliznykov вне форума Ответить с цитированием
Старый 11.01.2017, 16:01   #7
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

Цитата:
Так что ты уже сделал?
Он же показал вверху - ни чего. Один из способов проверки образуют ли 4 точки квадрат - вычисляешь шесть квадратов расстояний между ними. Если четыре из них равны между собой, а два других тоже равны между собой и в два раза больше, чем первое число - то квадрат. При чем расположенный произвольно. Просто теорема Пифагора.Если же стороны квадрата должны быть параллельны осям координат, то там совсем просто. И так в цикле по всем точкам
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар вне форума Ответить с цитированием
Старый 11.01.2017, 16:15   #8
ura_111
Участник клуба
 
Регистрация: 14.05.2016
Сообщений: 1,793
По умолчанию

Если тебе надо сначала ввести все точки ("... а мне нужно, чтобы после того как я задал точки..."), тогда лучше воспользоваться массивами:

0.jpg
ura_111 вне форума Ответить с цитированием
Старый 11.01.2017, 16:32   #9
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

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

p.s. кстати, проверка на то, что диагональ ровно в два раза больше - избыточно.
Если стороны равны и диагонали между собой равны - то это квадрат.
Но, разумеется, это утверждение верно!
AC^2 = BC^2 = 2*(AB^2) = 2*(BС^2) = 2*(СD^2) = 2*(DA^2)
Serge_Bliznykov вне форума Ответить с цитированием
Старый 11.01.2017, 17:03   #10
ura_111
Участник клуба
 
Регистрация: 14.05.2016
Сообщений: 1,793
По умолчанию

1.jpg

Нужно проверять все потенциальные 4-ки (в надежде что они окажутся квадратом).... но ты можешь (для начала) сделать только для первой 4-ки:
Код:
X[0]
Y[0]
X[1]
Y[1]
А потом перебор в Майн сделаешь.

p.s.: ну ты понял, да? У тебя, контрольный пример будет из 8-ми точек (как на картинке). Ты пишешь 2-е функции - 1-а проверяет по 4-м координатам квадрат ли это; а вторая функция считает кол-во точек.
Для начала в эти функции передай только первую 4-ку точек (а перебор потом сделаешь)...

Последний раз редактировалось ura_111; 11.01.2017 в 17:12.
ura_111 вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Выделить из заданных точек вершины квадрата, содержащего максимальное число заданных точек Kef1r C# (си шарп) 8 12.01.2017 16:00
Написать программу, которая определяет, попадает ли точка с заданными координатами в область, закрашенную на рисунке серым цветом. MegaMan123 Помощь студентам 4 10.06.2014 11:40
Написать программу, которая определяет, попадает ли точка с заданными координатами в область, закрашенную на рисунке серым цветом. d_dima Помощь студентам 1 05.03.2013 21:43
(С#)Написать программу, которая определяет, попадает ли точка с заданными координатами в область Nekro95 Помощь студентам 1 25.10.2012 11:00
написать программу..которая с использованием метода наименьших квадратов определяет параметры зависимости Марго Помощь студентам 3 14.10.2007 15:47