/*
Координаты вершин многоугольника :  (1,1)  (12,1) (10,10) (1,15)
Точки, через которые проходит прямая: (0,15) (1,18)
Набор точек:
Узлы сетки с шагом 1(0<=X<=20 и 0<=Y<=20)
Ограничение (R ) на расстояние между точками из набора точек и прямой:  4,2
Задание:
1)	Занести информацию о наборе точек в (номер точки в наборе и ее координаты) массив D1.
2)	Выбрать из набора точек все точки, лежащие внутри многоугольника и поместить полученную информацию 
    (номер точки в наборе и ее координаты) в массив D2.
3)	Вычислить расстояние r от каждой точки, занесенной в D2 до прямой. Информацию о всех точках, 
    для которых выполняется соотношение  r<=Rпоместить в массив D3, включающий в себя номер точки в D2, 
	номер точки в D1, координаты точки, расстояние от точки до прямой.
4)	Упорядочить D3 в порядке убывания r.
5)	Вывести результаты расчетов (пп.1-3) в виде таблиц на экран и в файл.

Требование к программе: 
1)	Ввод данных должен осуществляться из файла данных(набор точек) и с клавиатуры(уравнение прямой).
2)	Результаты расчета должны выводиться в виде таблиц на экран и в файл.
3)	Процедуры расчета расстояния r, выбора точек из массива D1, сортировки массива и вывод результатов 
    следует оформить в программе в форме функций пользователя.
Дополнительно:
Добавить в программу:
1)	Функцию расчета периметра и площади многоугольника.
2)	Функцию определения координат пересечения многоугольника с прямой, заданной с клавиатуры.
*/

#include	<iostream>
#include	<stdlib.h>
#include	<stdio.h>
#include	<conio.h>
#include	<math.h>

using namespace std;

//структура для хранения точки пересечения прямой с фигурой
typedef struct _FLOAT_POINT
{
	double	x;
	double	y;
}FLOAT_POINT;	

//структура для хранения точки
typedef struct _POINT
{
	int		x;
	int		y;
}POINT;	

//структура для хранения точки в массиве D2 и ее номера в массиве D1
typedef struct _COORD1
{
	int		num1;
	POINT	point;
}COORD1;

//структура для хранения точки в массиве D3, ее номеров в массивах D1 и D2 
typedef struct _COORD2
{
	int		num2;
	COORD1	Coord;
	double	r;
}COORD2;

#define	N				20	//верхняя граница области, нижняя - 0
#define	COUNT			4	//число вершин фигуры

#define LeftOriented	0	//ориентации
#define RightOriented	1

const double	EPS = 1.e-6;//для сравнения вещественных чисел на равенство

// Проверяем ориентацию вектора точки относительно вектора обхода грани
bool CheckOrientation(POINT *first, POINT *second)
{
	return (first->x*second->y - first->y*second->x)>0;	//>0 RightOriented
}

// Проверяем коллинеарность векторов
bool CheckCollinear(POINT *first, POINT *second)
{
	return first->x*second->y == first->y*second->x;
}

// Вычисляем координаты вектора относительно новой системы координат
void VectorSubstruct(POINT *from, POINT *to, POINT *res)
{
	res->x = to->x - from->x;
	res->y = to->y - from->y;
}

// Проверяем где находится точка Х относительно многогранника A с числом вершин count
// Возвращает
//-1 - вне
// 0 - на грани
// 1 - внутри
int Check(POINT *A, int count, POINT *x)
{
	POINT	AA, AX;				//временные вектора
	int		i, orientSum = 0;	//сложим все ориентации
	
	for (i=0; i<count; i++)		//по всем
	{
								//строим вектор AA = A[i] - A[i+1]
		if (i != count-1)		//кроме последней - с последующей
			VectorSubstruct(&A[i],&A[i+1],&AA);
		else					//последняя вершина с первой
			VectorSubstruct(&A[i],&A[0],&AA);
		VectorSubstruct(&A[i],x,&AX);	//строим вектор AX = A[i] - x
		//Если вектора коллинеарны - значит точка принадлежит грани
		if (CheckCollinear(&AA,&AX))
			return 0;			//на границе
								//складываем ориентации
		orientSum += CheckOrientation(&AA,&AX);
	}

	// Если все 4 ориентации векторов одинаковы (все=1 или все=0) - значит точка внутри четвероугольника
	if ((orientSum == 0) || (orientSum == 4))
		return 1;				//внутри
	else
		return -1;				//снаружи
}

//Последующие несколько функций расчитывают коэффициенты прямой Ax + Bx + C = 0
//исходя их координат двух точек
int	CalcA(POINT *line)
{
	return (line[0].y - line[1].y);
}
int	CalcB(POINT *line)
{
	return (line[1].x - line[0].x);
}
int	CalcC(POINT *line)
{
	return (line[0].y * (line[0].x - line[1].x) + line[0].x * (line[1].y - line[0].y));
}

//Расчет растоояния от точки X(x,y) до прямой, заданной двумя точками line
//r = (Ax+By+C)/sqrt(A^2+B^2)
double Distance(POINT *line, POINT *x)
{
	int		A = CalcA(line);
	int		B = CalcB(line);
	int		C = CalcC(line);

	return fabs((A*x->x + B*x->y + C)/sqrt((double)(A*A+B*B)));
}

//сортировка массива D3 методом "пузырька"
void Sort(COORD2 *d, int count)
{
	int		i, j;
	COORD2	w;

	for (i=0; i<count-1; i++)
		for (j=i+1; j<count; j++)
		{
			if (d[i].r < d[j].r)
			{
				w = d[i];
				d[i] = d[j];
				d[j] = w;
			}
		}
}

//расчет длины отрезка, заданного двумя точками
double Lenght(POINT *p1, POINT *p2)
{
	POINT pp;
	
	VectorSubstruct(p1, p2, &pp);					//разность векторов
	return (sqrt((double)(pp.x*pp.x + pp.y*pp.y)));	//длина разности
}

//расчет периметра фигуры, заданной массивом вершин и их количеством
double Perimeter(POINT *point, int count)
{
	int		i;
	double	p=0;

	for (i=0; i<count; i++)		//складываем длины отрезков
		p += (i == count-1)?Lenght(&point[i],&point[0]):Lenght(&point[i],&point[i+1]);
	
	return p;
}

//расчет площади
//разбиваем фигуру на треугольники, считаем площадь каждого по формуле Герона
//S = sqrt(p(p-a)(p-b)(p-c)), p = (a+b+c)/2
double Square(POINT *point, int count)
{
	int		i;
	double	p;
	double	s = 0;
	POINT	tr[3];				//вершины треугольника

	tr[0] = point[0];			//первая вершина одинаковая для всех
	for (i=1; i<=count-2; i++)	//разбиваем на треугольники
	{
		tr[1] = point[i];		//заполняем
		tr[2] = point[i+1];
		p = Perimeter(tr, 3) / 2;	//полупериод
								//складываем площади
		s += sqrt(p*(p-Lenght(&tr[0],&tr[1]))*
					(p-Lenght(&tr[1],&tr[2]))*
					(p-Lenght(&tr[2],&tr[0])));
	}
	return s;					//площадь всей фигуры
}

//расчет определителя матрицы 2х2
int det(int a00, int a01, int a10, int a11) 
{
	return a00 * a11 - a01 * a10;
}
 
//расчет точек пересечения линии line с max-угольной фигурой figure
//Функция возвращает число точек, сами точки - в points
//Если прямая совпадает с гранью, то возвращает -1
int intersect(POINT *figure, int max, POINT *line, FLOAT_POINT *points)
{
	int		i, j, k, z, count = 0;
	int		A1, B1, C1;				//коэффициенты уравнения прямых сторон
	int		A2 = CalcA(line);		//коэффициенты уравнения заданной прямой
	int		B2 = CalcB(line);
	int		C2 = CalcC(line);
	POINT	line1[2];
	double	x1, y1;
	
	//по всем отрезкам
	for	(i=0; i<max; i++)
	{
		if (i!=max-1)
		{
			line1[0] = figure[i];
			line1[1] = figure[i+1];
		}
		else
		{
			line1[0] = figure[i];
			line1[1] = figure[0];
		}
		A1 = CalcA(line1);			//коэффициенты уравнения прямой стороны
		B1 = CalcB(line1);
		C1 = CalcC(line1);
	
		z = det(A1, B1, A2, B2);
		if (z)						//есть пересечение с прямой
		{
									//точка пересечения
			x1 = - (double)det(C1, B1, C2, B2) / (double)z;
			y1 = - (double)det(A1, C1, A2, C2) / (double)z;
			//сначала проверим, есть ли такая точка
			for (j=0; j<count; j++)
			{	//сравнение вещественных чисел на совпадение нужно делать только так
				if ((fabs(x1 - points[j].x) < EPS) && (fabs(y1 - points[j].y) < EPS))
					break;
			}
			if (j < count)
				continue;			//нашли такую, идем на следующий отрезок
			points[count].x = x1;	//сохраним точку
			points[count].y = y1;
			//проверим, на участке отрезка ли она
			k = 0;					//признак попадания на отрезок
			//проверим концы отрезка
			if (((fabs((double)line1[0].x - x1) < EPS) && (fabs((double)line1[0].y - y1) < EPS)) || 
				((fabs((double)line1[1].x - x1) < EPS) && (fabs((double)line1[1].y - y1) < EPS)))
			{
				count++;			//да, вершина
				continue;			//идем дальше
			}
			else if (line1[0].x < line1[1].x)	//учтем порядок точек
			{						//на отрезке?
				if (((double)line1[0].x < x1) && ((double)line1[1].x > x1))
					k = 1;
			}
			else if (((double)line1[0].x > x1) && ((double)line1[1].x < x1))
				k = 1;
									//вертикальный отрезок
			else if (fabs((double)line1[0].x - x1) < EPS)
				k = 1;
			
			if (k)					//если попали по абциссе, проверим ординату
			{						//аналогично
				k = 0;
				if (line1[0].y < line1[1].y)
				{
					if (((double)line1[0].y < y1) && ((double)line1[1].y > y1))
						k = 1;
				}
				else if (((double)line1[0].y > y1) && ((double)line1[1].y < y1))
					k = 1;
				else if (fabs((double)line1[0].y - y1) < EPS)
					k = 1;
			}
			count += k;				//складываем. Если на отрезке, добавим 1
		}
		else						//определитель, равный 0, говорит о том,
		{							//что либо параллельно отрезку, либо
									//совпадает. Определимся.
			if (!det(A1, C1, A1, C1) && !det(B1, C1, B1, C1))
				return -1;			//совпадает с гранью!
		}
	}
	return	count;					//вернем число точек
}

//вводим точки из файла
int	GetFile(char *fName, POINT *points)
{
	int		i, count = 0;
	POINT	p;
	FILE	*fp = fopen(fName, "r") ;
	
	if (fp)
	{
		//в каждой строке по два числа
		while (-1 != fscanf(fp, "%d %d\n", &p.x, &p.y))
		{
			//принимаем только от 0 до N=20
			if (p.x < 0 || p.x > N || p.y < 0 || p.y > N)
				continue;
			//дубликаты пропускаем
			for (i=0; i<count; i++)
				if ((p.x == points[i].x) && (p.y == points[i].y))
					break;
			if (i != count)
				continue;		//нашли, значит пропускаем
			points[count++] = p;//сохраняем
		}
		fclose(fp);
	}
	return count;				//вернем число точек
}

//запрос целого числа с отбрасыванием всего того, что  >1000 и <-1000
int GetNum(char* str)
{
	char	line[256];
	int		a;
	do
	{
		a = -1000;
		cout << str;
		cin.getline(line, 256);
		a = atoi(line);
	}while (a <= -1000 || a > 1000);
	return a;
}

int	main()
{
	//четвероугольник
	POINT	poligon[COUNT] = {{1,1},{12,1},{10,10},{1,15}};
	//линия для расчета ближайших точек
	POINT	line[2] = {{0,15},{1,18}};
	//линия для расчета точек пересечения
	POINT	line2[2];
	//массивы для хранения точек. Максимум = числу точек в области [0,N]
	POINT	D1[(N+1)*(N+1)];
	COORD1	D2[(N+1)*(N+1)];
	COORD2	D3[(N+1)*(N+1)];
	//точки пересечения с фигурой. Их максимум 2, но задали, как число вершин
	FLOAT_POINT	inter_points[COUNT];
	char	buffer[128];
	double	r, R = 4.2;
	int		i, count;
	int		countD1, countD2, countD3;	//количество элементов в массивах
	FILE	*fp = fopen("points.log", "w") ;	//открываем файл журнала
	
	if (0 == fp)				//если ошибка, то выходим
	{
		cout << "Create file points.log error!" << endl;
		return 1;
	}
								//открываем файл данных
	if (0 == (countD1 = GetFile("points.txt", D1)))
	{							//если ошибка, то выходим!
		fclose(fp);
		cout << "File points.txt not found!" << endl;
		return 2;
	}

	//проверяем, какие из точек попадают в фигуру
	for(countD2=i=0; i<=countD1; i++)
	{
		if (1 == Check(poligon, COUNT, &D1[i]))	//учитываем только внутренние
		{
			D2[countD2].num1 = i;				//сохраняем в массиве D2
			D2[countD2++].point = D1[i];
		}
	}
	//Ищем точки, близкие к прямой line
	for(countD3=i=0; i<countD2; i++)
	{
		if ((r=Distance(line, &D2[i].point))<=R)//r <= R
		{
			D3[countD3].num2 = i;				//сохраняем в массиве D3
			D3[countD3].Coord = D2[i];
			D3[countD3++].r = r;
		}
	}
	Sort(D3, countD3);							//сортируем массив D3 по расстоянию

//выводим все результаты и на экран, и в файл
	cout << "D1:" << endl;
	fputs("D1:\n", fp);
	for(i=0; i<countD1; i++)
	{
		sprintf(buffer, "x =%3d, y =%3d\n", D1[i].x, D1[i].y);
		cout << buffer;			//на экран
		fputs(buffer, fp);		//в файл
	}

	cout << "D2:" << endl;
	fputs("D2:\n", fp);
	for(i=0; i<countD2; i++)
	{
		sprintf(buffer, "D1[%3d], x =%3d, y =%3d\n", D2[i].num1, 
			D2[i].point.x, D2[i].point.y);
		cout << buffer;
		fputs(buffer, fp);
	}

	cout << "D3:" << endl;
	fputs("D3:\n", fp);
	for(i=0; i<countD3; i++)
	{
		sprintf(buffer, "D2[%3d], D1[%3d], x =%3d, y =%3d, r =%6.3f\n", D3[i].num2, 
			D3[i].Coord.num1, D3[i].Coord.point.x, D3[i].Coord.point.y, D3[i].r);
		cout << buffer;
		fputs(buffer, fp);
	}

//периметр
	sprintf(buffer, "\nPerimeter = %7.3f\nSquare    = %7.3f\n", 
		Perimeter(poligon, COUNT), Square(poligon, COUNT));
	cout << buffer;
	fputs(buffer, fp);

//площадь
//запросим координаты двух точек
	cout << endl << "Enter line for crossing search" << endl
		 << "Enter two points:" << endl;
	line2[0].x = GetNum("X1 = ");
	line2[0].y = GetNum("Y1 = ");
	line2[1].x = GetNum("X2 = ");
	line2[1].y = GetNum("Y2 = ");
//выводим точки введенной прямой
	sprintf(buffer, "Line (%d,%d)-(%d,%d)\n", 
		line2[0].x, line2[0].y, line2[1].x, line2[1].y);
	cout << buffer;
	fputs(buffer, fp);
//ищем точки пересечения
	count = intersect(poligon, COUNT, line2, inter_points);
//выводим результат
	if (count == -1)		//прямая совпадаем с одной из граней
	{
		printf("The line coincides with one of the parties of a figure\n");
		fputs("The line coincides with one of the parties of a figure\n", fp);
	}
	else if (count == 0)	//прямая не пересекает фигуру
	{
		cout << endl << "No crossings of a line with a figure" << endl;
		fputs("\nNo crossings of a line with a figure\n", fp);
	}
	else					//точки найдены
	{
		cout << "\nCrossing of a line with a figure are: ";
		fputs("\nCrossing of a line with a figure are: ", fp);
		for (i=0; i<count; i++)
		{
			sprintf(buffer,"(%7.3f, %7.3f) ", inter_points[i].x, inter_points[i].y);
			cout << buffer;
			fputs(buffer, fp);
		}
		cout << endl;
		fputs("\n", fp);
	}
	fclose(fp);
	cout << "Press any key" << endl;
	getch();
	return 0;
}

2 4
20 2
1 2
0 15
6 7
14 20
5 10
1 12
2 13
0 14
1 12
2 11