O(n*m*k) solution is AC. Rating 731 is too big. Very simple geometry task

The test 1 is different, and checks this condition.

If N = M = 1, then 1 ≤ K ≤ min(M*N-1, 1000) = 0.

In test 2 my solution fails because of some trash in testfile after usefull information. Please, fix that.

Is example in problem right? I think it is not!!!

Where am i wrong? It should be obvious :) because it is WA2

#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <iostream>
#include <fstream>
#include <iterator>
#include <math.h>
#include <cstdio>
#include <cstdlib>
#include <sstream>

using namespace std;
const double eps=1e-6;

struct R{
    int x;
    int y;
    double r;
};

R r[1111];
int a[55][55];
bool s[55][55];
int n,m,k,x,y;

int main(){
    cin>>n>>m>>k;
    for(int i=0;i<m;i++)
        for(int j=0;j<n;j++)
            cin>>a[i][j];
    for(int i=0;i<k;i++){
        cin>>r[i].x>>r[i].y>>r[i].r;
        r[i].x--;r[i].y--;
        s[r[i].x][r[i].y]=true;
    }
    long res=0;
    for(int i=0;i<m;i++)
        for(int j=0;j<n;j++)
            if(!s[i][j]){
                bool possible=true;
                double d;
                int mina=a[i][j];
                int maxa=32000;
                int _mna,_mxa;
                for(int q=0;q<k;q++){
                    d=r[q].r*r[q].r-(i-r[q].x)*(i-r[q].x)-(j-r[q].y)*(j-r[q].y);
                    if(d<-eps) {possible=false;break;}
                    d=floor(sqrt(d+eps))+eps;
                    _mna=d;_mna=a[r[q].x][r[q].y]-_mna;
                    _mxa=d;_mxa=a[r[q].x][r[q].y]+_mxa;
                    if(mina<_mna) mina=_mna;
                    if(maxa>_mxa) maxa=_mxa;
                    if(mina>maxa) {possible=false;break;}
                }
                if(possible)
                    res+=(maxa-mina+1);
            }

    cout<<res<<endl;
    return 0;
}

Edited by author 01.07.2007 04:19

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.

const inp='';
type fff=record
          x,y:integer;
          r:real;
         end;
var
 map:array[1..50,1..50]of integer;
 fsz:array[1..1000]of fff;
 z:array[1..1000,1..2]of integer;
 n,m,max,k:integer;
 t:text;

procedure zl;
 var i,j:longint;
  begin
   fillchar(map,sizeof(map),0);
   fillchar(z,sizeof(z),0);
   fillchar(fsz,sizeof(fsz),0);
   assign(t,inp);
   reset(t);
   readln(t,m,n,k);
   for i:=1 to m do
    for j:=1 to n do
     read(t,map[i,j]);
   for i:=1 to k do readln(t,fsz[i].x,fsz[i].y,fsz[i].r);
   close(t);
  end;

procedure gc;
 var i,j,l,min,big:longint;
     s:real;
     yes:boolean;
 begin
  for i:=1 to m do
   for j:=1 to n do
    begin
     fillchar(z,sizeof(z),0);
     yes:=true;
     for l:=1 to k do
      if (fsz[l].x<>i)or(fsz[l].y<>j) then
      begin
       s:=sqr(fsz[l].r)-sqr(i-fsz[l].x)-sqr(j-fsz[l].y);
       if s>=0 then
       begin
        z[l,1]:=round(-sqrt(s)+map[fsz[l].x,fsz[l].y]+0.49);
        z[l,2]:=trunc(sqrt(s)+map[fsz[l].x,fsz[l].y]);
        if z[l,1]<map[i,j] then z[l,1]:=map[i,j];
        if z[l,2]<map[i,j] then begin
                                 yes:=false;
                                 break;
                                end
       end else begin
                 yes:=false;
                 break;
                end;
      end
     else begin
           yes:=false;
           break;
          end;
     if yes then
     begin
      min:=z[1,1];big:=z[1,2];
      for l:=2 to k do
      begin
       if min<z[l,1] then min:=z[l,1];
       if big>z[l,2] then big:=z[l,2];
      end;
      if (big>=min)and yes then max:=max+(big-min)+1;
     end;
   end;
 end;

begin
 zl;
 gc;
 writeln(max);
end.
please tell me why?

const
        maxn=50;
type
        integer=longint;
var
        map,d,f:array[1..maxn,1..maxn] of integer;
        u:array[1..maxn,1..maxn] of boolean;
        p:array[1..maxn,1..2] of integer;
        r:array[1..maxn] of extended;
        n,m,k,tot:integer;
procedure init;
var     i,j:integer;
begin
        readln(n,m,k);
        for i:=1 to n do
                for j:=1 to m do read(map[i,j]);
        fillchar(u,sizeof(U),0);
        for i:=1 to k do begin
                read(p[i,1],p[i,2],r[i]);
                u[p[i,1],p[i,2]]:=true;
        end;
end;
procedure solve;
var     i,j,now,npos:integer;
        dis,h:extended;
begin
        for i:=1 to n do for j:=1 to m do d[i,j]:=maxlongint;
        fillchar(f,sizeof(f),0);
        for now:=1 to k do
                for i:=1 to n do
                        for j:=1 to m do if not u[i,j] then begin
                                dis:=sqrt(sqr(p[now,1]-i)+sqr(p
[now,2]-j));
                                if (dis>r[now])or(sqrt(sqr(dis)+sqr
(map[p[now,1],p[now,2]]-map[i,j]))>r[now])and(map[i,j]>=map[p
[now,1],p[now,2]]) then continue;
                                inc(f[i,j]);
                                h:=map[p[now,1],p[now,2]]+sqrt(sqr(r
[now])-sqr(dis));
                                npos:=trunc(h)-map[i,j]+1;
                                if npos<d[i,j] then d[i,j]:=npos;
                        end;
        tot:=0;
        for i:=1 to n do
                for j:=1 to m do if (not u[i,j])and(f[i,j]=k) then
inc(tot,d[i,j]);
        writeln(tot);
end;
begin
        init;
        solve;
end.