ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1331. Vladislava

How to avoid TLE?(-)
Posted by Maigo Akisame (maigoakisame@yahoo.com.cn) 20 Oct 2004 15:09
Use double instead of extended (-)
Posted by Dmitry 'Diman_YES' Kovalioff 20 Oct 2004 16:46
But I use real everywhere and do as much pre-calculation as possible. It's still TLE on test #4.
Posted by Maigo Akisame (maigoakisame@yahoo.com.cn) 21 Oct 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 (-)
Posted by Dmitry 'Diman_YES' Kovalioff 21 Oct 2004 22:25
Calling "min" function slows your program (-)
Posted by Michael Rybak (accepted@ukr.net) 25 Oct 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.
Posted by Maigo Akisame (maigoakisame@yahoo.com.cn) 26 Oct 2004 04:39
Use octtree structure (+)
Posted by Korduban [Kiev] 7 Feb 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" (-)
Posted by Ariel 8 Feb 2005 00:11
Could you mail your AC code to dkorduban [at] ukr.net? (-)
Posted by Korduban [Kiev] 8 Feb 2005 15:56
Accepted in 0.171 (+)
Posted by Korduban [Kiev] 9 Feb 2005 17:41
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.