Задача Пересечение окружностей
Задан набор из 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.