program ural1331;
const
  maxm=5000;
  zero=1e-6;
var
  w,l,x,y,z:array[1..maxm]of real;
  n,m,i,j:word;
  r,ww,ll,xx,yy,zz,ans:real;
procedure calcoord(var w,l,x,y,z:real);
  begin
    w:=w*pi/180;
    l:=l*pi/180;
    x:=cos(w)*cos(l);
    y:=cos(w)*sin(l);
    z:=sin(w);
  end;
function min(a,b:real):real;
  begin
    if a<b then min:=a else min:=b;
  end;
function arcsin(s:real):real;
  begin
    if s>1-zero then
      arcsin:=pi/2
    else
      arcsin:=arctan(s/sqrt(1-s*s));
  end;
begin
  read(n,m,r);
  for i:=1 to m do begin
    read(w[i],l[i]);
    calcoord(w[i],l[i],x[i],y[i],z[i]);
  end;

  for i:=1 to n do begin
    read(ww,ll);
    calcoord(ww,ll,xx,yy,zz);
    ans:=1e38;
    for j:=1 to m do
      ans:=min(ans,sqr(xx-x[j])+sqr(yy-y[j])+sqr(zz-z[j]));
    writeln(arcsin(sqrt(ans)/2)*2*r:0:2);
  end;
end.

Edited by author 26.10.2004 00:27

subj. My program get AC in 0.302 (without optimizations). I think it's possible to reduce time to 0.150 sec

http://acm.timus.ru/status.aspx?space=1&pos=737505



Edited by author 07.02.2005 23:03

Middle time of speed can be taken by using
simple qsort of points by key=max(y[i],i=1,..3)
and then log-time search of pozition of point x[k]
under consideration in sorted array with
cutting off parts of array y which
far enough from the pozition.