Обсуждение @ 1331. Владислава @ Timus Online Judge

How to avoid TLE?(-)

Послано Maigo Akisame (maigoakisame@yahoo.com.cn) 20 окт 2004 15:09

Use double instead of extended (-)

Послано Dmitry 'Diman_YES' Kovalioff 20 окт 2004 16:46

But I use real everywhere and do as much pre-calculation as possible. It's still TLE on test #4.

Послано Maigo Akisame (maigoakisame@yahoo.com.cn) 21 окт 2004 04:45

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.

There are a lot of calculations in your program - optimize it (-)

Послано Dmitry 'Diman_YES' Kovalioff 21 окт 2004 22:25

Calling "min" function slows your program (-)

Послано Michael Rybak (accepted@ukr.net) 25 окт 2004 23:02

Edited by author 26.10.2004 00:27

Thanks. I use dot product this time and deleted the min/max function. Ac in 0.671s.

Послано Maigo Akisame (maigoakisame@yahoo.com.cn) 26 окт 2004 04:39

Use octtree structure (+)

Послано Korduban [Kiev] 7 фев 2005 23:01

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

Strange! My brute force got AC in 0.39. And what is it "octtree structure" (-)

Послано Ariel 8 фев 2005 00:11

Could you mail your AC code to dkorduban [at] ukr.net? (-)

Послано Korduban [Kiev] 8 фев 2005 15:56

Accepted in 0.171 (+)

Послано Korduban [Kiev] 9 фев 2005 17:41

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

Re: Accepted in 0.171 (+)

Послано svr 20 ноя 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.

Обсуждение задачи 1331. Владислава