Задача Пересечение окружностей
Задан набор из N окружностей, которые описываются координатами своих центров. Все окружности имеют одинаковый радиус R. Необходимо найти две окружности, площадь пересечения которых максимальная. На рисунке красным цветом отображается область пересечения двух окружностей.
Формат ввода:
N R
X[1] Y[1]
X[2] Y[2]
…
X[N] Y[N]
N – Количество окружностей
R – Радиус окружностей
X[i] Y[i] – центр i-ой окружности
Ограничения:
2 <= N < = 100
0 <= X[i] Y[i] R <= 1000
Все числа целые.
Формат вывода:
Ответ на задачу - номера окружностей, площадь пересечения которых максимальная.
Пример ввода:
3 1
0 0
1 0
1 1
Пример вывода:
1 2
var x,y:array[1..1000] of longint; n,i,r,n2,n1,j:longint; minp,p:real;
begin
readln(n,r);
for i:=1 to n do
readln(x[i],y[i]);
minp:=sqrt( (x[1]-x[2])*(x[1]-x[2])+(y[1]-y[2])*(y[1]-y[2]) );
n1:=1;
n2:=2;
for i:=1 to n do
for j:=1 to n do
begin
p:=sqrt( (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]) );
if (minp >p)and(i<>j) then begin
minp:=p;
n1:=i;
n2:=j;
end;
end;
writeln(n1,' ',n2);
end.