ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1168. Radio Stations

i don't think my program have got TLE
Послано Koala 24 авг 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
Послано hello 19 май 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.