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 1168. Radio Stations

i don't think my program have got TLE
Posted by Koala 24 Aug 2003 14:29
program p1168;

const
  maxn=50;
  zero=1e-6;

var
  low,high,h:array [1..maxn,1..maxn] of longint;
  visit:array [1..maxn,1..maxn] of boolean;
  m,n,k,i,j,pp,i1,j1,ans,low1,high1:longint;
  d,r,dh:real;

  function dis(x1,y1,x2,y2:longint):real;
  begin
    dis:=sqrt(sqr(x1-x2)+sqr(y1-y2));
  end;

  function ceiling(k:real):longint;
  begin
    if abs(k-round(k))<=zero
      then ceiling:=round(k)
      else ceiling:=trunc(k)+1;
  end;

  function floor(k:real):longint;
  begin
    if abs(k-round(k))<=zero
      then floor:=round(k)
      else floor:=trunc(k);
  end;

begin
  read(m,n,k);
  for i:=1 to m do
    for j:=1 to n do
    begin
      read(h[i,j]);
      low[i,j]:=h[i,j]; high[i,j]:=maxlongint;
    end;

  fillchar(visit,sizeof(visit),0);
  for pp:=1 to k do
  begin
    read(i,j,r);
    visit[i,j]:=true;
    for i1:=1 to m do
      for j1:=1 to n do
        if (i<>i1) or (j<>j1) then
        begin
          d:=dis(i,j,i1,j1);
          if r>=d-zero
            then begin
              dh:=sqrt(sqr(r+zero)-sqr(d));
              low1:=ceiling(h[i,j]-dh); high1:=floor(h[i,j]+dh);
              if high1<high[i1,j1] then high[i1,j1]:=high1;
              if low1>low[i1,j1] then low[i1,j1]:=low1;
            end
            else high[i1,j1]:=low[i1,j1]-1;
        end;
  end;

  ans:=0;
  for i:=1 to m do
    for j:=1 to n do
      if not(visit[i,j]) and (high[i,j]>=low[i,j])
        then inc(ans,high[i,j]-low[i,j]+1);
  writeln(ans);
end.
Re: i don't think my program have got TLE
Posted by hello 19 May 2004 17:41
Thank you for your solution.
I find my mistake by your solution.
I got AC.
if you want , I can post my solution to you.