//Даны N точек на плоскости. Найти среди них точки являющиеся вершинами фигуры, содержащей максимальное число заданных точек. 
//Фигура - параллелограмм.
//Гребовод Алексей
//ФКТИ 2301
// 10.01.2012

#include <iostream>
#include <math.h>
#include <fstream>
using namespace std;
const int N=250;

ifstream inx; // Файл с координатами X
ifstream iny; // Файл с координатами Y
ofstream par; // Файл с полученными параллелограммами
ofstream maxpar; // Файл с максимальным параллелограммом
ofstream to4k; // Файл с точками, которые принадлежат параллелограмму
ofstream polu4; // Файл со всеми точками

double in(double X[N], double Y[N], double  n) // Начало функции ввода
{
 inx.open("D://files//7lab//inx.txt"); // Открытие файла с координатами x
 iny.open("D://files//7lab//iny.txt"); // Открытие файла с координатами y
 polu4.open("D://files//7lab//polu4.txt");

  int i;
  double z;

  for(i=0; i<n; i++) // Начало цикла ввода
  {
   if((inx.eof()!=0)||(iny.eof()!=0)) { cout << " Преждевременный конец файла " << endl; exit(1); }
   else
   {
    inx >> z;   // Ввод Х
    X[i] = z;

    iny >> z;  // Вод У
    Y[i] = z;
     }
   polu4 << "(" << X[i] << "; " << Y[i] << ");" << endl;
  }

  return 0;
} // Конец функции ввода




//длина стороны АВ
double side(double xa, double ya, double xb, double yb)
{return sqrt((xb-xa)*(xb-xa)+(yb-ya)*(yb-ya));}

//отклонение С от АВ
double deviation(double x1, double y1, double x2, double y2, double x3, double y3)
{
    double r=side(x1,y1,x2,y2);
    double A=(y2-y1)/r;
    double B=(x2-x1)/r;
    double C=(x1*(y2-y1)-y1*(x2-x1))/r;
    return (x3*A-y3*B-C);
}



double process( double X[N], double Y[N],  double K[N],  double n, double kol=0)
{ par.open("D://files//7lab//par.txt");
to4k.open("D://files//7lab//to4k.txt");
maxpar.open("D://files//7lab//maxpar.txt");
maxpar << "Максимального параллелограма не обнаружено" << endl;
maxpar.close();
   int i, j, u, h, c=0;
   int i1, j1 , u1, h1;
   double max;
   max=0;
    for(i=0; i<(n-3); i++) // Цикл
   {
     for(j=(i+1); j<(n-2); j++) // Который
  {
   for(u=(i+2); u<(n-1); u++) // Меня
   {
    for(h=(i+3); h<n; h++) // Задолбал
    {

     if((side(X[i],Y[i],X[j],Y[j])==0)||(side(X[i],Y[i],X[u],Y[u])==0)||(side(X[i],Y[i],X[h],Y[h])==0)||(side(X[j],Y[j],X[u],Y[u])==0)||(side(X[j],Y[j],X[h],Y[h])==0)||(side(X[u],Y[u],X[h],Y[h])==0)){ break;}
     // Проверка на совпадение точек


     // Нахождение Коэффициентов наклона 1-4
     if(X[j]!=X[i]) 
     {
     K[1]=(Y[j]-Y[i])/(X[j]-X[i]);
     }
     else( K[1]=(Y[j]-Y[i]));

     if(X[h]!=X[u])
     {
     K[2]=(Y[h]-Y[u])/(X[h]-X[u]);
     } else ( K[2]=(Y[h]-Y[u]) );
   

        if(X[u]!=X[i])
     {
     K[3]=(Y[u]-Y[i])/(X[u]-X[i]);
     } else ( K[3]=(Y[u]-Y[i]));
     
     if(X[h]!=X[j])
     {
     K[4]=(Y[h]-Y[j])/(X[h]-X[j]);
     }else(  K[4]=(Y[h]-Y[j]));
    
     // Конец нахождения наклонов



       // Расчёт длинн сторон
    double L_IJ=sqrt((X[j]-X[i])*(X[j]-X[i]) + (Y[j]-Y[i])*(Y[j]-Y[i])); 
    double L_HU=sqrt((X[u]-X[h])*(X[u]-X[h]) + (Y[u]-Y[h])*(Y[u]-Y[h]));
    double L_IH=sqrt((X[h]-X[i])*(X[h]-X[i]) + (Y[h]-Y[i])*(Y[h]-Y[i]));
    double L_JU=sqrt((X[u]-X[j])*(X[u]-X[j]) + (Y[u]-Y[j])*(Y[u]-Y[j]));




// Проверка на нахождение точек на одной прямой
double dev12_3 = deviation(X[i],Y[i],X[j],Y[j],X[u],Y[u]);
double dev12_4 = deviation(X[i],Y[i],X[j],Y[j],X[h],Y[h]);
double dev23_4 = deviation(X[j],Y[j],X[u],Y[u],X[h],Y[h]);
double dev13_4 = deviation(X[i],Y[i],X[u],Y[u],X[h],Y[h]);
if(dev12_3==0 || dev12_4==0 || dev23_4==0 || dev13_4==0) break;

//if(((L_IJ==L_HU)&&(L_IH==L_JU))||((L_IJ==L_JU)&&(L_IH==L_HU))||((L_IJ==L_IH)&&(L_HU==L_JU)))
// Если коэффициенты наклона равны
if(((K[1]==K[2])&&(K[3]==K[4]))||((K[1]==K[3])&&(K[2]==K[4]))||((K[1]==K[4])&&(K[2]==K[3])))
{

 par << "Параллелограмм" << endl;
 par << "(" << X[i] << "; " << Y[i] << ");" << endl;
 par << "(" << X[j] << "; " << Y[j] << ");" << endl;
 par << "(" << X[u] << "; " << Y[u] << ");" << endl;
 par << "(" << X[h] << "; " << Y[h] << ");" << endl;


 kol=0;
 for(i1=0; i1<n; i1++)
 { 

  // Начинается самое интересное


  // Нахождение длин сторон, с которыми точка образует треугольники
  double L_Xi=sqrt(pow((X[i]-X[i1]),2) + pow((Y[i]-Y[i1]),2)); 
     double L_Xj=sqrt(pow((X[j]-X[i1]),2) + pow((Y[j]-Y[i1]),2));
  double L_Xh=sqrt(pow((X[h]-X[i1]),2) + pow((Y[h]-Y[i1]),2));
  double L_Xu=sqrt(pow((X[u]-X[i1]),2) + pow((Y[u]-Y[i1]),2));


  // Нахождение полупериметров этих треугольников
  double p_xij=(L_Xi+L_Xj+L_IJ)/2;
  double p_xih=(L_Xi+L_Xh+L_IH)/2;
  double p_xhu=(L_Xh+L_Xu+L_HU)/2;
  double p_xuj=(L_Xu+L_Xj+L_JU)/2;


  // Нахождение площадей этих треугольников
  double s_xij=sqrt(p_xij*(p_xij-L_Xi)*(p_xij-L_Xj)*(p_xij-L_IJ));
  double s_xih=sqrt(p_xih*(p_xih-L_Xi)*(p_xih-L_Xh)*(p_xih-L_IH));
  double s_xhu=sqrt(p_xhu*(p_xhu-L_Xh)*(p_xhu-L_Xu)*(p_xhu-L_HU));
  double s_xuj=sqrt(p_xuj*(p_xuj-L_Xu)*(p_xuj-L_Xj)*(p_xuj-L_JU));
  double sobch=s_xij+s_xih+s_xhu+s_xuj;

  // Осталось найти площадь параллелограмма... Уже 4 часа утра, делать мне нечего, разобью и его на 2 треугольника
        double L_HJ=sqrt(pow((X[h]-X[j]),2) + pow((Y[h]-Y[j]),2)); // Длина диагонали
        double p_hij=(L_IH+L_HJ+L_IJ)/2;  // Нахождение полупериметра треуголника
  double s_hij=sqrt(p_hij*(p_hij-L_IH)*(p_hij-L_HJ)*(p_hij-L_IJ)); // Площадь треугольника

  double spar=2*s_hij; 
 
  if(spar>=sobch)
  {
   kol=kol+1; 
   if(max<kol)
   {  
   max=kol;
   to4k << "(" << X[i1] << "; " << Y[i1] << "); " << endl;

 maxpar.open("D://files//7lab//maxpar.txt");
 maxpar << "Максимальный параллелограмм" << endl;
 maxpar << "(" << X[i] << "; " << Y[i] << ");" << endl;
 maxpar << "(" << X[j] << "; " << Y[j] << ");" << endl;
 maxpar << "(" << X[u] << "; " << Y[u] << ");" << endl;
 maxpar << "(" << X[h] << "; " << Y[h] << ");" << endl;
   maxpar.close();
   }
   
  }
 
 }
}}}}} // Честно, сам запутался, какая от чего, но столько радости ^^


   par.close();
   return 0;
}



void main()
{
setlocale(LC_ALL, "");

double x[N],y[N],k[N], kol;
double n, l=1, max;
kol=0;
cout << "Введите количество точек" << endl;
do
{   cin >> n;

    if(n<3)
 {
 cout << " Мало точек " << endl;
 }

 if(l==3)
 {
 cout << " n=4" << endl;
 cout << "Поехали? " << endl;
 system&#40;"pause"&#41;;
 }
 l++;
}while(n<3);

in(&x[0], &y[0], n);
process(&x[0], &y[0], &k[0], n, kol);
}