But I use real everywhere and do as much pre-calculation as possible. It's still TLE on test #4.
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.
Re: Accepted in 0.171 (+)
Posted by
svr 20 Nov 2006 14:32
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.