Программа
{ ЛЭТИ
исходные данные в текстовом файле
определяют окружность (три вещественных в первой строке)
множество точек (пары вещественных в последующих строках)
выбрать точки, определяющие прямые для которых количества точек лежащих
по разные стороны прямой и в окружности имеют наименьшую разность }
CONST N=100; { Количество точек (размер массива) }
TYPE Circle_Type = record { Тип - окружность }
X, Y: real; { Координаты центра }
R: real; { Радиус окружности }
end;
Point_Type = record { Тип - точка }
Init: boolean; { Флаг инициализации координат }
X, Y: real; { Координаты }
Used_In_Line: boolean; { Флаг использования точки
в определении найденных линий }
Circle_Flag: boolean; { Флаг принадлежности точки окружности }
end;
Point_Array_Type = array [1..N] of Point_Type; { Тип - массив точек }
PROCEDURE Make_Data(var F: text); { Процедура набора исходного файла }
Function Rnd:real; begin Rnd:=Random*10 end;
{ Функция определения случайного числа в полузакрытом интервале [0..10[ }
Var i: word; { Счетчик }
Begin
Randomize; { Инициализация генератора случайных чисел }
Rewrite(F); { Открытие файла под запись }
WriteLn(F,Rnd:5:2,' ',Rnd:5:2,' ',Rnd:5:2); { Запись параметров окружности }
for i:=1 to Random(N+1) do WriteLn(F,Rnd:5:2,' ',Rnd:5:2);
{ Цикл определения координат точек }
Close(F) { Закрытие файла }
End;
PROCEDURE Input_Data(var F: text; var Circle: Circle_Type; var A: Point_Array_Type);
{ Процедура ввода (получения) данных }
Var i: word; { Счетчик элементов массива }
Begin
Reset(F); { Открытие файла под чтение }
with Circle do ReadLn(F, X, Y, R); { Чтение "окружности" }
for i:=1 to N do { Цикл чтения координат точек }
with A[i] do { Снятие префикса записи в массиве (упрощение доступа к полям записи A[i]) }
if EOF(F) { Проверка достижения конца файла }
then Init:=FALSE { "Определение незаданной точки" }
else begin
Init:=TRUE; { Подъем флага определенной точки }
Used_In_Line:=FALSE;
{ Сброс флага использования точки для определения линии }
ReadLn(F, X, Y); { Чтение точки }
Circle_Flag:=Sqr(X-Circle.X)+Sqr(Y-Circle.Y)<Sqr(Circle.R)
{ Определение принадлежности точки к кругу }
end;
Close(F) { Закрытие файла }
End;
FUNCTION Sign(x:real):integer; { Функция - Сигнатура }
Begin
if x<0 then Sign:=-1
else if x=0 then Sign:=0
else Sign:=1
End;
FUNCTION Get_Side(X1, Y1, X2, Y2, X, Y: real):integer; { Функция определения
"стороны", с которой находится точа (X,Y) относительно прямой [(X1,Y1),(X2,Y2)]:
-1 - точка находится "ниже или левее";
0 - прямая неопределена или точка лежит на прямой;
1 - точка находится "выше или правее"}
Begin
if (X1=X2)and(Y1=Y2) or (X1=X)and(Y1=Y) or (X=X2)and(Y=Y2)
{ Проверка совпадения точек (неопределенность прямой или принадлежность
точки (X,Y) к заданной прямой) }
then Get_Side:=0
else if Abs(X1-X2)>Abs(Y1-Y2) { Селектор выбора критерия оценки
относительного положения точки - "выше/ниже" или "левее/правее",
по углу наклона прямой}
then Get_Side:=Sign(Y1+(Y2-Y1)/(X2-X1)*(X-X1)-Y) { Оценка "выше/ниже" }
else Get_Side:=Sign(X1+(X2-X1)/(Y2-Y1)*(Y-Y1)-X);{ Оценка "левее/правее" }
End;
FUNCTION Get_Difference(L1, L2: word; P: Point_Array_Type):integer;
{ Определение разности между количествами точек, лежащих по разные стороны,
относительно прямой [L1,L2] }
Var Difference:integer; { Разность }
i: 1..N; { Счетчик точек }
Begin
Difference:=0; { Сброс разности }
for i:=1 to N do { Цикл просмотра массива точек }
if P[i].Circle_Flag { Проверка принадлежности текущей точки к кругу }
then Difference:=Difference+
+Get_Side(P[L1].X, P[L1].Y, P[L2].X, P[L2].Y, P[i].X, P[i].Y)
{ Набор разности }
else;
Get_Difference:=Abs(Difference); { Определение значения функции }
End;
FUNCTION CheckCrossing(L1,L2:Point_Type;Circle:Circle_Type):boolean;
{ Функция проверки пересечения прямой (L1 L2) окружности Circle,
сравнением расстояния от центра до прямой с радиусом }
Var A,B,C:real;
Begin
A:=L2.Y-L1.Y;
B:=L1.X-L2.X;
C:=L2.X*L1.Y-L1.X*L2.Y;
with Circle do
CheckCrossing:=(Abs(A*X+B*Y+C)/Sqrt(Sqr(A)+Sqr(B)))<R
End;
PROCEDURE Process_Data(C: Circle_Type; var P: Point_Array_Type;
var Output_Line, Output_Not_Used_Point: text);
{ Процедура обработки данных }
Var Min_Difference, Difference: word; { Наименшая найденная и текущая разности
количества точек, лежащих по разные стороны относительно исследуемой прямой }
i, k: 1..N; { Счетчики точек в массиве }
Label Finish; { Метка для выхода из вложенного цикла перебора возможных прямых }
Begin
Min_Difference:=N; { Начальное определение наименьшей разности }
for i:=1 to N-1 do { Цикл перебора возможных линий (перебор "начальных" концов отрезков)
для определения наименьшей разности количества точек находящихся по разные стороны
прямых для всех возможных прямых }
if P[i].Init { Проверка определенности точки }
then for k:=i+1 to N do { Цикл перебора возможных "конечных" концов отрезков }
if P[k].Init { Проверка определенности точки }
and CheckCrossing(P[i],P[k],C)
then begin
Difference:=Get_Difference(i, k, P);
{ Определение разности количества точек, находящихся по
разные стороны от прямой, определённой i-ой и k-ой точками }
{ Если новая разность меньше предыдущей, то - переопределение
наименьшей разности: }
if Difference<Min_Difference
then begin
Min_Difference:=Difference;
{ Досрочный выход из внешнего цикла при достижении
наименьшего возможного значения: }
if Difference=0
then GoTo Finish
else;
end
else;
end
else Break { Досрочный выход из цикла, т.к. неопределенные
точки могут находится только в конце массива }
else Break; { Досрочный выход из цикла, т.к. неопределенные
точки могут находится только в конце массива }
Finish:; { Метка для выхода из цикла }
Rewrite(Output_Line); { Открытие файла для вывода списка линий }
for i:=1 to N-1 do { Цикл перебора возможных линий (перебор "начальных" концов отрезков)
для поиска линий с наименьшей разностью количества точек находящихся по разные стороны
прямых для всех возможных прямых }
begin
if P[i].Init { Проверка определенности точки }
then for k:=i+1 to N do { Цикл перебора возможных "конечных" концов отрезков }
if P[k].Init { Проверка определенности точки }
and CheckCrossing(P[i],P[k],C)
then if Get_Difference(i, k, P)=Min_Difference
{ Проверка соответствия прямой определенному критерию }
then begin
{ Подъём флагов принадлежности точек найденой прямой: }
P[i].Used_In_Line:=TRUE;
P[k].Used_In_Line:=TRUE;
WriteLn(Output_Line, P[i].X:5:2, ' ', P[i].Y:5:2, ' ', P[k].X:5:2, ' ', P[k].Y:5:2)
{ Вывод координат прямой в файл }
end
else
else Break { Досрочный выход из цикла, т.к. неопределенные
точки могут находится только в конце массива }
else Break { Досрочный выход из цикла, т.к. неопределенные
точки могут находится только в конце массива }
end;
Close(Output_Line); { Закрытие файла линий }
Rewrite(Output_Not_Used_Point);
{ Открытие файла для вывода списка неиспользованных точек }
for i:=1 to N do { Цикл вывода неиспользуемых точек }
with P[i] do { Снятие префикса для доступа к полям записи }
if not Used_In_Line and Init { Проверка определенности точки и её
неиспользования в прямых }
then WriteLn(Output_Not_Used_Point, X:5:2, ' ', Y:5:2) { Вывод координат точки }
else;
Close(Output_Not_Used_Point); { Закрытие файла точек }
End;
VAR Circle: Circle_Type; { Окружность }
A: Point_Array_Type; { Массив точек }
Input, { Входной файл }
Output_Line, { Выходной файл прямых }
Output_Not_Used_Point: text; { Выходной файл неиспользованных точек }
BEGIN
{ Связывание файловых переменных с именами файлов: }
Assign(Input,'INPUT.txt');
Assign(Output_Line,'LINES.txt');
Assign(Output_Not_Used_Point, 'POINT.txt');
(* Make_Data(Input); { Создание файла исходных данных } *)
Input_Data(Input, Circle, A); { Ввод исходных данных }
Process_Data(Circle, A, Output_Line, Output_Not_Used_Point); { Обработка данных }
END.
Бесплатные примеры программ
Примеры написанных программ
Помощь студентам по программированию