Структуры, точки, квадраты, подробности в описании

[svjat32]

Задано множество точек на плоскости. Найти все четверки точек, являющихся вершинами квадратов. Найти квадрат, внутри которого лежит наибольшее количество точек множества.
Необходимо решить эту задачу ОБЯЗАТЕЛЬНО с использованием структур.
Друзья, если не поможете, мне, скорее всего, пи**ец(((

[Romeo]

Ну самое простое, что приходит в голову, это организовать 4 вложенных цикла, покрывающие наш промежуток от 0 до N-1 четырьма непекрывающимися интервалами.

Код: Выделить всё

for (int i1 = 0; i1 < N-3; ++i1)
   for (int i2 = i1+1; i2 < N-2; ++i2)
      for (int i3 = i2+1; i3 < N-1; ++i3)
         for (int i4 = i3+1; i4 < N; ++i4)
         {
            // check and count
         }

И внутри проверять являются ли точки, хранящиеся в массиве по индексам i1, i2, i3, i4 вершинами квадрата. Условие проверки будет достаточно громоздкое, но соорудив его первую часть, остальные части получатся обычным копипастом и последующим подправлением, так что ничего сложного там нет.

Проверить точки, которые лежат внутри нашего квадрата, можно напиписав дополнительный цикл по j.

Код: Выделить всё

for (int j = 0; j < N; ++j)
   if (j != i1 && j != i2 && j != i3 && j != i4)
   {
      // if we are there, then j-th point is not an angle of the current square
      // so we can check whether this point is inside the square and increment some counter in case of true
   }

[svjat32]

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

[Romeo]

Повторений не будет. Посмотри внимательно, i2 не от нуля бежит, а от i1+1.

Второй фрагмент кода использует i1, i2, i3, i4, значит он должен быть внутри вложенных циклов.

Пожалуй, вернусь чуть позже и опишу полностью алгоритм на верхнем уровне, но опустив детали нижнего уровня.

[svjat32]

Повторений не будет. Посмотри внимательно, i2 не от нуля бежит, а от i1+1.

а вторая часть пожалуйста помогите, куда ее писать?

[Romeo]

Что-то я начал писать, вошёл во вкус и написал больше, чем собирался. Тебе осталось дописать самому код всего в трёх местах, там где в коментах написано TODO. Что именно должно быть написано, так же указано в коментариях. Ну и, само собой, для того, чтобы дописать, придётся разобраться сначала в том, что уже есть, а сей факт особенно радует моё скрытое преподавательское эго

Код: Выделить всё

#include <iostream>

const inst MAX_N = 20;

struct Point
{
   int x, y;
};

struct Rect
{
   int left, right, top, bottom;
};

bool TryToFormSquare(const Point& p1, const Point& p2, const Point& p3, const Point& p4, Rect& rect)
{
   // TODO: implement
   // Tries to form square from points p1, p2, p3, p4. If it is possible, fills rect variable with
   // correct coordinates and returns true. Otherwise returns false.
}

bool IsPointInsideRect(const Point& p, const Rect& rect)
{
   // TODO: implement
   // Returns true if point is inside rect and false otherwise.
}

int main()
{
   Point points[MAX_N];

   int N = 0;
   // TODO: Read array points from keyboard here
   // Also fill N with number of actually entered points (it can be less then MAX_N)

   int maxPointsInRect = -1;
   int maxPoint1 = 0;
   int maxPoint2 = 0;
   int maxPoint3 = 0;
   int maxPoint4 = 0;

   Rect rect;

   for (int i1 = 0; i1 < N-3; ++i1)
      for (int i2 = i1+1; i2 < N-2; ++i2)
          for (int i3 = i2+1; i3 < N-1; ++i3)
             for (int i4 = i3+1; i4 < N; ++i4)
               if (TryToFormSquare(points[i1], points[i2], points[i3], points[i4], rect))
               {
                  std::cout << "Found rectange. Indexes of points: " <<
                            << i1 << ", " << i2 << ", " << i3 << ", " << i4 << std::endl;

                  int pointsInRect = 0;
               
                  for (int j = 0; j < N; ++j)
                     if (j != i1 && j != i2 && j != i3 && j != i4)
                        if (IsPointInsideRect(points[j], rect))
                           ++pointsInRect;
               
                  if (pointsInRect > maxPointsInRect)
                  {
                     maxPointsInRect = pointsInRect;
                     maxPoint1 = i1;
                     maxPoint2 = i2;
                     maxPoint3 = i3;
                     maxPoint4 = i4;
                  } 
               }

   if (maxPointsInRect == -1)
   {
      std::cout << "No rectangles are found" << std::endl;
   }
   else
   {
      std::cout << "Maximus points number inside a rectagle is " << maxPointsInRect 
                << ". Rectange is built from points with indexes " 
                << maxPoint1 << ", " << maxPoint2 << ", " << maxPoint3 << ", " << maxPoint4 << std::endl
   }

   return 0;
}

[somewhere]

Эх, жаль завтра времени не будет. А так бы осилил TryToFormSquare. Задача интересная и путей решения тоже много.

[svjat32]

Огромное спасибо, еще маленький вопрос, как делать проверку на точку в фигуре? Корректно ли будет разбивать каждый квадрат на треугольники, проверять сумму площадей, и если меньше - принадлежит, иначе - нет???
плюс еще что за rect ??? если я правильно понял это структура квадратов, тогда в ее объявлении должно быть написано Point p1, p2, p3, p4
плюс мне нужны не индексы, а координаты.
помогите)

За вторую часть еще не брался, проверьте что не так в нахождении квадратов, при вводе координат (2,0) ; (2,2); (0,2); (0,0) квадрат не находит((((

Код: Выделить всё

#include "stdafx.h"
#include <iostream>
using namespace std;
const int MAX_N = 20;

struct Point
{
   int x, y;
};

struct Rect
{
   float left, right, top, bottom;
};

bool TryToFormSquare(const Point& p1, const Point& p2, const Point& p3, const Point& p4, Rect& rect)
{
   if ((sqrt((p2.x-p1.x)*(p2.x-p1.x)+(p2.y-p1.y)*(p2.y-p1.y)))==(sqrt((p3.x-p2.x)*(p3.x-p2.x)+(p3.y-p2.y)*(p3.y-p2.y)))==(sqrt((p4.x-p3.x)*(p4.x-p3.x)+(p4.y-p3.y)*(p4.y-p3.y)))==(sqrt((p1.x-p4.x)*(p1.x-p4.x)+(p1.y-p4.y)*(p1.y-p4.y))))
   {return true;}
   else if ((sqrt((p1.x-p3.x)*(p1.x-p3.x)+(p1.y-p3.y)*(p1.y-p3.y)))==(sqrt((p3.x-p2.x)*(p3.x-p2.x)+(p3.y-p2.y)*(p3.y-p2.y)))==(sqrt((p4.x-p2.x)*(p4.x-p2.x)+(p4.y-p2.y)*(p4.y-p2.y)))==(sqrt((p1.x-p4.x)*(p1.x-p4.x)+(p1.y-p4.y)*(p1.y-p4.y))))
   {return true;}
   else if ((sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)))==(sqrt((p4.x-p2.x)*(p4.x-p2.x)+(p4.y-p2.y)*(p4.y-p2.y)))==(sqrt((p3.x-p4.x)*(p3.x-p4.x)+(p3.y-p4.y)*(p3.y-p4.y)))==(sqrt((p1.x-p3.x)*(p1.x-p3.x)+(p1.y-p3.y)*(p1.y-p3.y))))
   {return true;}
   else {return false;}
}

/*bool IsPointInsideRect(const Point& p, const Rect& rect)
{
   // TODO: implement
   // Returns true if point is inside rect and false otherwise.
}
*/
int main()
{
 //  Point points[MAX_N];

   int N = 0;
   cout<<"input point\n";
	cin>>N;
	Point *points=new Point[N];
	cout<<"Please, enter N points:\n";
	for(int i=0;i<N;i++)
	{cin>>points[i].x>>points[i].y;}

   int maxPointsInRect = -1;
   int maxPoint1 = 0;
   int maxPoint2 = 0;
   int maxPoint3 = 0;
   int maxPoint4 = 0;

   Rect rect;

   for (int i1 = 0; i1 < N-3; ++i1)
      for (int i2 = i1+1; i2 < N-2; ++i2)
          for (int i3 = i2+1; i3 < N-1; ++i3)
             for (int i4 = i3+1; i4 < N; ++i4)
               if (TryToFormSquare(points[i1], points[i2], points[i3], points[i4], rect))
               {
                  cout << "Found rectange. Indexes of points: " << points[i1].x <<" "<<points[i1].y << ", "<< points[i2].x <<" "<<points[i2].y << ", " << points[i3].x <<" "<<points[i3].y << ", " << points[i4].x <<" "<<points[i4].y << ", " << endl;

                 /* int pointsInRect = 0;
               
                  for (int j = 0; j < N; ++j)
                     if (j != i1 && j != i2 && j != i3 && j != i4)
                        if (IsPointInsideRect(points[j], rect))
                           ++pointsInRect;
               
                  if (pointsInRect > maxPointsInRect)
                  {
                     maxPointsInRect = pointsInRect;
                     maxPoint1 = i1;
                     maxPoint2 = i2;
                     maxPoint3 = i3;
                     maxPoint4 = i4;
                  } */
               }

 /*  if (maxPointsInRect == -1)
   {
     cout << "No rectangles are found" << endl;
   }
   else
   {
      cout << "Maximus points number inside a rectagle is " << maxPointsInRect << ". Rectange is built from points with indexes " << maxPoint1 << ", " << maxPoint2 << ", " << maxPoint3 << ", " << maxPoint4 << endl;
   }
   */
   return 0;
}

[somewhere]

при вводе координат (2,0) ; (2,2); (0,2); (0,0) квадрат не находит((((

Сравнение иррациональных чисел происходит не всегда корректно. Вместо сравнения x == y нужно сравнивать abs(x - y) < E, а лучше оформить это в виде функции.

[Romeo]

1. Почему не работает сравнение?
Помимо того, что числа с плавающей точкой действительно нельзя сравнивать на равенство, есть ещё один пункт. В C++ невозможно сравнение, которое мы в математике привыкли записывать a == b == c. Точнее такая запись возможна, но она даёт не то, что мы ожидаем. Компилятор разбивает такую конструкцию на операторы справа налево и выполняет сначала проверку b == c. Её результат типа bool имеет значения true или false. Далее он понимает, что программист хочет, чтобы мы сравнили a с булевым значением и поэтому он автоматически приводит a к bool (если ноль, то false, иначе true) и проверяет равно ли это тому булевому значение, которое мы получили на предыдущем шаге. Ясное дело, это совсем не то, что мы хотим. Для того, чтобы проверка работала так, как мы ожидаем, выражение следует переписать так: (a == b) && (a == c), где && - логическое И.

По той причине, что а у тебя будет фигурировать в выражении два раза, рекомендую сделать локальные переменные, в которые сохранить вычисленные длины сторон. А потом сравнивать эти переменные.

Ещё один совет, который поможет уйти от проблемы сравнения чисел с плавающей точкой. Как ты верно заметил, по теореме Пифагора, взяв сумму квадратов катетов (которыми являются проекции отрезка на координатные оси), мы получаем квадрта гипотенузы (нашего отрезка). До сих мы ещё находимся в области целых числах. Но чтобы узнать длину отрезка, нужно вычислить корень, от полученного выражения. И вот тут мы выходим в область иррациональных чисел. Внимание вопрос. Нужна ли нам длина отрезка или нам нужно лишь узнать равны ли длины двух отрезков или нет? Конечно нам нужно только ответ да или нет, сама длина не нужна. Следующий вопрос. Если две гипотенузы равны, равны ли их квадраты? Да. А обратное справедливо? Да, справедливо, так как гипотенузы с отрицательной длиной мы не рассматриваем. Намёк понятен? Сравнивай подкоренные выражения и ты останешься в области целых чисел.

2. Что такое Rect и почему там всего 4 целые числа, а не 4 пары чисел?
Дело в том, что я посчитал, что задание проще, чем на самом деле. Мне показалось, что следует проверять только квадраты, у которых стороны параллельны координатным осям. Если это не так, то замечание вполне справедливое. Более того, тогда можно избавиться от структуры Rect, а вместо неё передавать в IsPointInsideRect 4 наши точки.

3. Как понять находится ли точка, внутри квадрата.
Идею ты дал совершенно верную. Триангулировать квадрат, получив два треугольника. Затем проверить находится ли точка либо в одном, либо в другом треугольнике. По поводу того, как определить лежит ли точка внутри треугольника, как я понял, ничего объяснять не надо. Ангем, первый курс. Хочу лишь заострить внимание на процессе триангуляции. Если у нас есть 4 точки p1, p2, p3, p4, и мы сделали из них две тройки (p1, p2, p3) и (p2, p3, p4), то нам крайне важно, чтобы общая сторона (в нашем случае это p2p3), являлась диагональю квадрата. Думаю, объяснять, почему это важно, не стоит. Просто не забудь сделать дополнительную проверку. Как её сделать, тоже понятно, надеюсь. Взять любую точку. Из неё к остальным точкам идут 2 стороны и диагональ. Затем проверить длины любых двух отрезков, исходящих из этой точки. Если они не равны, то диагональ - это больший из неравных отрезок. Если равны, то диагональ - это третий отрезок. Не бойся для проверок заводить временные переменные, в том числе типа Point - это упростит код.