олимпиадники-информатики

Задача Пересечение окружностей


Задан набор из 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.