// миллионная переработка.cpp: определяет точку входа для консольного приложения.
//

#include "stdafx.h"
#include <iostream>
using namespace std;


struct Point
{
   float x, y;
};
double e=0;
float dest(const Point& p1, const Point& p2)
{
    return (sqrt((p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y)));


}
bool TryToFormSquare(const Point& p1, const Point& p2, const Point& p3, const Point& p4)
{
    if ((abs(dest(p2, p1) - dest(p2, p3))<=e) && (abs(dest(p2, p3) - dest(p4, p3))<=e) && (abs(dest(p4, p3) - dest(p4, p1))<=e) && (abs(dest(p3, p1) - dest(p2, p4))<=e))
   {return true;}
    else if ((abs(dest(p3, p1) - dest(p2, p3))<=e) && (abs(dest(p2, p3) - dest(p2, p4))<=e) && (abs(dest(p2, p4) - dest(p1, p4))<=e) && (abs(dest(p2, p1) - dest(p3, p4))<=e))
   {return true;}
    else if ((abs(dest(p2, p1) - dest(p2, p4)) <= e) && (abs(dest(p2, p4) - dest(p3, p4)) <= e) && (abs(dest(p3, p4) - dest(p3, p1)) <= e) && (abs(dest(p1, p4) - dest(p3, p2)) <= e))
   {return true;}
   else {return false;}
}
float HalfPerim(float a, float b, float c)
{
    return ((a+b+c)/2);
}

float square(const Point& p, const Point& p2, const Point& p4)
    {
    return (sqrt(HalfPerim(dest(p, p2), dest(p, p4), dest(p2, p4))*((HalfPerim(dest(p, p2), dest(p, p4), dest(p2, p4))) - dest(p, p2))*((HalfPerim(dest(p, p2), dest(p, p4), dest(p2, p4))) - dest(p2, p4))*((HalfPerim(dest(p, p2), dest(p, p4), dest(p2, p4))) - dest(p, p4))));


    }


bool IsPointInsideRect(const Point& p, const Point& p1, const Point& p2, const Point& p3, const Point& p4)
{

    if ((abs(dest(p2, p1) - dest(p2, p3)) <= e) && (abs(dest(p2, p3) - dest(p4, p3)) <= e) && (abs(dest(p4, p3) - dest(p4, p1)) <= e) && (abs(dest(p3, p1) - dest(p2, p4)) <= e))
    {
        if ((square(p, p2, p4)) >= (square(p, p1, p3)))
        {
            if ((square(p, p2, p4)) <= ((dest(p1, p2)*dest(p1, p2)) / 2))
            {
                return true;
            }
            else return false;

        }
        else
        {
            if ((square(p, p2, p4)) < (square(p, p1, p3)))
            {
                if ((square(p, p1, p3)) <= ((dest(p1, p2)*dest(p1, p2)) / 2))
                {
                    return true;
                }
                else return false;
            }

        }
    }
    else if ((abs(dest(p3, p1) - dest(p2, p3)) <= e) && (abs(dest(p2, p3) - dest(p2, p4)) <= e) && (abs(dest(p2, p4) - dest(p1, p4)) <= e) && (abs(dest(p2, p1) - dest(p3, p4)) <= e))
    {
        {
            if ((square(p, p1, p2)) >= (square(p, p3, p4)))
            {
                if ((square(p, p1, p2)) <= ((dest(p1, p3)*dest(p1, p3)) / 2))
                {
                    return true;
                }
                else return false;

            }
            else
            {
                if ((square(p, p1, p2)) < (square(p, p3, p4)))
                {
                    if ((square(p, p1, p2)) <= ((dest(p1, p3)*dest(p1, p3)) / 2))
                    {
                        return true;
                    }
                    else return false;
                }

            }
        }
    }
    else if ((abs(dest(p2, p1) - dest(p2, p4)) <= e) && (abs(dest(p2, p4) - dest(p3, p4)) <= e) && (abs(dest(p3, p4) - dest(p3, p1)) <= e) && (abs(dest(p1, p4) - dest(p3, p2)) <= e))
    {
        {
            if ((square(p, p2, p3)) >= (square(p, p1, p4)))
            {
                if ((square(p, p2, p3)) <= ((dest(p1, p2)*dest(p1, p2)) / 2))
                {
                    return true;
                }
                else return false;

            }
            else
            {
                if ((square(p, p2, p3)) < (square(p, p1, p4)))
                {
                    if ((square(p, p2, p3)) <= ((dest(p1, p2)*dest(p1, p2)) / 2))
                    {
                        return true;
                    }
                    else return false;
                }

            }
        }
    }
    else { return false; }
}
struct squarer
{
    Point p1, p2, p3, p4;


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

   int maxPointsInRect = -1;
   float maxPoint1x = 0;
   float maxPoint1y = 0;
   float maxPoint2x = 0;
   float maxPoint2y = 0;
   float maxPoint3x = 0;
   float maxPoint3y = 0;
   float maxPoint4x = 0;
   float maxPoint4y = 0;

 int temp = 0;
   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]))
               {
                  cout << "Found rectange with points. Coordinates 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;

                      temp++;
                      quader[temp].p1 = points[i1];
                      quader[temp].p2 = points[i2];
                      quader[temp].p3 = points[i3];
                      quader[temp].p4 = points[i4];


                  int pointsInRect = 0;

                  for (int j = 0; j < N; ++j)
                     if (j != i1 && j != i2 && j != i3 && j != i4)
                        if (IsPointInsideRect(points[j], points[i1], points[i2], points[i3], points[i4]))
                           ++pointsInRect;

                  if (pointsInRect > maxPointsInRect)
                  {
                     maxPointsInRect = pointsInRect;
                     maxPoint1x = points[i1].x;
                     maxPoint1y = points[i1].y;
                     maxPoint2x = points[i2].x;
                     maxPoint2y = points[i2].y;
                     maxPoint3x = points[i3].x;
                     maxPoint3y = points[i3].y;
                     maxPoint4x = points[i4].x;
                     maxPoint4y = points[i4].y;
                  }
               }

               if ((maxPointsInRect == -1) || (maxPointsInRect == 0))
   {
     cout << "No rectangles are found" << endl;
   }
   else
   {
       cout << "Maximus points number inside a rectagle is " << maxPointsInRect << "." << endl << " Rectange is build from points with coordinates " << maxPoint1x << " " << maxPoint1y << ", " << maxPoint2x << " " << maxPoint2y << ", " << maxPoint3x << " " << maxPoint3y << ", " << maxPoint4x << " " << maxPoint4y << endl;
   }
               cout << endl << endl << endl << endl;
               for (int i = 1; i <= temp; i++)
               {
                   cout << quader[i].p1.x << " " << quader[i].p1.y << "; " << quader[i].p2.x << " " << quader[i].p2.y << "; " << quader[i].p3.x << " " << quader[i].p3.y << "; " << quader[i].p4.x << " " << quader[i].p4.y << endl;
               }
delete[] points;

return 0;
}