Найти две такие точки, чтобы две окружности с центрами в точках удовлетворяли условию - PascalABC.NET
Формулировка задачи:
есть такая задача, которую сейчас думаю как решить:
4) Дано множество точек на плоскости. Найти две такие точки, чтобы две окружности заданного радиуса, с центрами в этих точках были такими, что количество точек внутри окружностей было одинаковым.
Возник вопрос: 1) Как быть с точками, что находятся на самой окружности(считать или нет); 2) Можно ли как-то разом сократить время выполнения( что-то проверить) и 3) Можно ли, чтобы окружности пересекались?
Подскажите, если вы компетентны, пожалуйста!Решение задачи: «Найти две такие точки, чтобы две окружности с центрами в точках удовлетворяли условию»
textual
Листинг программы
(* Дано множество точек на плоскости. Найти две такие точки,
чтобы две окружности заданного радиуса, с центрами в этих точках были такими,
что количество точек внутри окружностей было одинаковым.*)
program z4;
uses graphABC;
const
n = 5;//максимальное число точек
r = 100;//вы рисуете окружности радиусрм 100, а не 200
w = 700;//размеры графического окна
type
tochki = array[1..2,1..n] of integer;
//точка внутри окружности
function inside(x,y,tx,ty:integer):boolean;
begin
result:=sqr(x-tx)+sqr(y-ty)<r*r
end;
//количество точек в окружности
function count(tx,ty:integer;a:tochki;n:integer):integer;
var i:integer;
begin
result:=-1;//вычитаем точку в центре
for i:=1 to n do
if inside(a[1,i],a[2,i],tx,ty)then inc(result)
end;
var k: tochki;
i, j: integer;
m:set of byte;//номера точек, около которых есть нужные окружности
begin
setwindowsize(400,400);
centerwindow;
writeln('Введите ', n, ' координат Х от ',r,' до ',w-r);
for i := 1 to n do
readln(k[1, i]);
writeln('Введите ', n, ' координат Y от ',r,' до ',w-r);
for i := 1 to n do
readln(k[2, i]);
writeln('press enter');
writeln('Даны координаты:');
for i := 1 to n do
writeln(i, '(', k[1, i], ';', k[2, i], ')');
m:=[];
for i:=1 to n-1 do
for j:=i+1 to n do
if (count(k[1,i],k[2,i],k,n)>0)and(count(k[1,i],k[2,i],k,n)=count(k[1,j],k[2,j],k,n)) then
begin
writeln('точки ',i,' ',j,' по ',count(k[1,i],k[2,i],k,n),' тч.');
m:=m+[i]+[j];
end;
if m=[] then writeln('Нет окружностей сравным количеством точек внутри');
writeln('press enter');
readln;
ClearWindow;
setwindowsize(w,w);
centerwindow;
setbrushstyle(bsClear);
for i := 1 to n do
begin
SetPenColor(clBlue);
Circle(k[1, i], k[2, i], 3);
textout(k[1, i]+5, k[2, i], inttostr(i));
if i in m then SetPenColor(clRed)
else SetPenColor(clBlack);
Circle(k[1, i], k[2, i], r);
end;
end.
Объяснение кода листинга программы
- Программа на языке PascalABC.Net.
- Задано множество точек на плоскости.
- Необходимо найти две такие точки, чтобы две окружности заданного радиуса, с центрами в этих точках, удовлетворяли условию - количество точек внутри окружностей было одинаковым.
- Точка внутри окружности - это функция, которая проверяет, находится ли точка внутри окружности по заданным координатам центра и радиусу.
- Количество точек в окружности - это функция, которая подсчитывает количество точек внутри окружности по заданным координатам центра.
- Ввод координат точек происходит с клавиатуры.
- Переменная
mпредставляет собой множество номеров точек, около которых есть нужные окружности. - Циклы перебирают все возможные комбинации точек для проверки условия.
- Если количество точек внутри окружностей совпадает, то выводится сообщение с номерами точек и количеством точек внутри окружностей.
- Переменная
mобновляется, если найдены нужные окружности. - Если
mпустое, выводится сообщениеНет окружностей сравным количеством точек внутри. - Очистка окна и рисование окружностей и их центров с помощью функций графического модуля.
- Цикл перебирает все точки для рисования окружностей и их центров.
- Черный цвет используется для окружностей, красный - для точек, удовлетворяющих условию.
- Программа завершается после нажатия клавиши Enter.