Здравствуйте, Посетитель - 349343!
Так как точки только в сетке с шагом 1, то для хранения точек используются целые числа,
кроме точек пересечения, где использованы вещественные.
Программа вводит обязательный файл points.txt с точками и формирует файл points.log с копией информации на экране.
В файле допустимы только целые числа из интервала [0,20]
Запрашивает координаты двух точки из области [0:20,0:20], через которую проходит прямая.
После чего находит точки пересечения прямой с четвероугольником.
[code h=207]/*
Координаты вершин многоугольника : (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;
}
[/code]
Примерный файл points.txt