2
8 0 0
8 100 0

Answer: 11600

CONST
  BigNum = 31337;
VAR
  N, I, J : LongInt;
  X, Y, R : ARRAY[1..1010] OF Extended;
  MinX, MaxX, MinY, MaxY, cX, cY : Extended;
  SMinX, SMaxX, SMinY, SMaxY, Best, Sum : Extended;
LABEL L1, L2, L3, L4;
BEGIN
  ReadLn(N);
  ReadLn(R[1], X[1], Y[1]);
  MinX := X[1]-R[1];
  MaxX := X[1]+R[1];
  MinY := Y[1]-R[1];
  MaxY := Y[1]+R[1];
  FOR I := 2 TO N DO
    BEGIN
      ReadLn(R[I], X[I], Y[I]);
      IF X[I]-R[I] < MinX THEN MinX := X[I]-R[I];
      IF X[I]+R[I] > MaxX THEN MaxX := X[I]+R[I];
      IF Y[I]-R[I] < MinY THEN MinY := Y[I]-R[I];
      IF Y[I]+R[I] > MaxY THEN MaxY := Y[I]+R[I];
    END;
  IF ((MaxX-MinX) <= 100) AND ((MaxY-MinY) <= 100) THEN
    BEGIN
      Write(100*100);
      Halt;
    END;
  SMaxX := MaxX;
  SMaxY := MaxY;
  SMinX := MinX;
  SMinY := MinY;
  IF (SMaxX-SMinX) < 100 THEN SMaxX := SMinX+100;
  IF (SMaxY-SMinY) < 100 THEN SMaxY := SMinY+100;
  Best := (SMaxX-SMinX)*(SMaxY-SMinY);
  FOR I := 1 TO N DO
    BEGIN
      cX := X[I]+R[I];
      cY := Y[I]-R[I];
      SMinX := +BigNum;
      SMaxX := -BigNum;
      SMinY := +BigNum;
      SMaxY := -BigNum;
      FOR J := 1 TO N DO
        BEGIN
          IF ((X[J]+R[J]) <= cX) AND (Y[J]-R[J] >= cY) THEN Continue;
          IF (X[J]-R[J] < cX) AND (Y[J]-R[J] >= cY) AND
          (X[J]+R[J] > cX) THEN GOTO L1;
          IF (X[J]+R[J] <= cX) AND (Y[J]+R[J] > cY) AND
          (Y[J]-R[J] < cY) THEN GOTO L1;
          IF X[J]-R[J] < SMinX THEN SMinX := X[J]-R[J];
          IF X[J]+R[J] > SMaxX THEN SMaxX := X[J]+R[J];
          IF Y[J]-R[J] < SMinY THEN SMinY := Y[J]-R[J];
          IF Y[J]+R[J] > SMaxY THEN SMaxY := Y[J]+R[J];
        END;
      IF SMinX = BigNum THEN Continue;
      IF (SMinX < cX) AND (SMaxY > cY) THEN Continue;
      IF (SMaxX-SMinX) < 100 THEN SMaxX := SMinX+100;
      IF (SMaxY-SMinY) < 100 THEN SMaxY := SMinY+100;
      IF (cX-MinX) < 100 THEN cX := MinX+100;
      IF (MaxY-cY) < 100 THEN cY := MaxY-100;
      Sum := (SMaxX-SMinX)*(SMaxY-SMinY)+(cX-MinX)*(MaxY-cY);
      IF (Best > Sum) THEN Best := Sum;
L1:
    END;
  FOR I := 1 TO N DO
    BEGIN
      cX := X[I]+R[I];
      cY := Y[I]+R[I];
      SMinX := +BigNum;
      SMaxX := -BigNum;
      SMinY := +BigNum;
      SMaxY := -BigNum;
      FOR J := 1 TO N DO
        BEGIN
          IF ((X[J]+R[J]) <= cX) AND (Y[J]+R[J] <= cY) THEN Continue;
          IF (X[J]-R[J] < cX) AND (Y[J]+R[J] <= cY) AND
          (X[J]+R[J] > cX) THEN GOTO L2;
          IF (X[J]+R[J] <= cX) AND (Y[J]+R[J] > cY) AND
          (Y[J]-R[J] < cY) THEN GOTO L2;
          IF X[J]-R[J] < SMinX THEN SMinX := X[J]-R[J];
          IF X[J]+R[J] > SMaxX THEN SMaxX := X[J]+R[J];
          IF Y[J]-R[J] < SMinY THEN SMinY := Y[J]-R[J];
          IF Y[J]+R[J] > SMaxY THEN SMaxY := Y[J]+R[J];
        END;
      IF SMinX = BigNum THEN Continue;
      IF (SMinX < cX) AND (SMinY < cY) THEN Continue;
      IF (SMaxX-SMinX) < 100 THEN SMaxX := SMinX+100;
      IF (SMaxY-SMinY) < 100 THEN SMaxY := SMinY+100;
      IF (cX-MinX) < 100 THEN cX := MinX+100;
      IF (cY-MinY) < 100 THEN cY := MinY+100;
      Sum := (SMaxX-SMinX)*(SMaxY-SMinY)+(cX-MinX)*(cY-MinY);
      IF (Best > Sum) THEN Best := Sum;
L2:
    END;
  FOR I := 1 TO N DO
    BEGIN
      cX := X[I]-R[I];
      cY := Y[I]-R[I];
      SMinX := +BigNum;
      SMaxX := -BigNum;
      SMinY := +BigNum;
      SMaxY := -BigNum;
      FOR J := 1 TO N DO
        BEGIN
          IF ((X[J]-R[J]) >= cX) AND (Y[J]-R[J] >= cY) THEN Continue;
          IF (X[J]-R[J] < cX) AND (Y[J]-R[J] >= cY) AND
          (X[J]+R[J] > cX) TH

in this test ther is only one pictures need, like this:
input:
1
100 0 0

output:
40000

GOOD LUCK!!!

>2
0 0 8
2 2 6
My output: 10000

3
745 852 22
49 235 549
856 460 11
My output: 3412016

Looks like std::vector::rend() does not return const_reverse_iterator.
I have got CE on the line
for( std::vector< Spot >::const_reverse_iterator it = spots.rbegin(); it != spots.rend(); ++it )
but
for( std::vector< Spot >::/*const_*/reverse_iterator it = spots.rbegin(); it != spots.rend(); ++it )
was ok.

приведение, живущее в доме
->
привидение, живущее в доме

it appeares when you count area wrongly for one spot with r > 50

first picture have coordinates
(0, 0), (300, 100)
S1 = 30000
and second picture have coordinates
(140, 240), (160, 260)
S2 = 400

S1 + S2 = 30400
30400 < 40000.

Why I don't right?
(Sorry my bad english).

In description:
A spot is described by three positive integers; they are the radius of the spot and the Cartesian coordinates of the center of the spot. Everything is measured in millimeters and all these numbers do not exceed 10000.

I have tested many times. But in test 7 one of x or y coordinates is negative!

Please, check

2
50 50 50
100 200 100

ans = 50000

Task says that "spot is described by three positive integers". But it is only difference between my AC and WA programs! (test #8)

type point=record
             x,y,r:longint;
           end;

var a:array[1..1000] of point;
    l,r:array[1..1000] of longint;
    lx,rx:array[1..1000] of record
                              up,low:longint;
                            end;
    x1,x2,y1,y2,n,i:longint;
    ans,s:extended;

function min(a,b:longint):longint;
begin
  if a>b then min:=b
  else min:=a;
end;

function max(a,b:longint):longint;
begin
  if a>b then max:=a
  else max:=b;
end;

procedure qsort(r,p,flag:longint);
var i,j:longint;
    k,t:point;

  function bigger(a,b:point;flag:longint):boolean;
  begin
    bigger:=(flag=1) and (a.x>=b.x) or (flag=2) and (a.y>=b.y);
  end;

begin
  k:=a[random(p-r+1)+r];
  i:=r-1;
  j:=p+1;
  repeat
    repeat inc(i); until bigger(a[i],k,flag);
    repeat dec(j); until bigger(k,a[j],flag);
    if i<j then
    begin
      t:=a[i];
      a[i]:=a[j];
      a[j]:=t;
    end;
  until i>=j;
  if r<j then qsort(r,j,flag);
  if j+1<p then qsort(j+1,p,flag);
end;

begin
  readln(n);
  for i:=1 to n do
    readln(a[i].r,a[i].x,a[i].y);
  randomize;
  qsort(1,n,1);
  fillchar(l,sizeof(l),0);
  fillchar(r,sizeof(r),0);
  fillchar(lx,sizeof(lx),0);
  fillchar(rx,sizeof(rx),0);
  r[1]:=a[1].x+a[1].r;
  for i:=2 to n do
    r[i]:=max(a[i].x+a[i].r,r[i-1]);
  l[n]:=a[n].x-a[n].r;
  for i:=n-1 downto 1 do
    l[i]:=min(a[i].x-a[i].r,l[i+1]);
  lx[1].up:=a[1].y+a[1].r;
  lx[1].low:=a[1].y-a[1].r;
  for i:=2 to n do
  begin
    lx[i].up:=max(a[i].y+a[i].r,lx[i-1].up);
    lx[i].low:=min(a[i].y-a[i].r,lx[i-1].low);
  end;
  rx[n].up:=a[n].y+a[n].r;
  rx[n].low:=a[n].y-a[n].r;
  for i:=n-1 downto 1 do
  begin
    rx[i].up:=max(a[i].y+a[i].r,rx[i+1].up);
    rx[i].low:=min(a[i].y-a[i].r,rx[i+1].low);
  end;
  ans:=(r[n]-l[1])*(lx[n].up-lx[n].low);
  for i:=1 to n-1 do
  if r[i]<l[i+1] then
  begin
    x1:=max(r[i]-l[1],100);
    y1:=max(lx[i].up-lx[i].low,100);
    x2:=max(r[n]-l[i+1],100);
    y2:=max(rx[i+1].up-rx[i+1].low,100);
    s:=x1*y1+x2*y2;
    if s<ans then ans:=s;
  end;
  qsort(1,n,2);
  fillchar(l,sizeof(l),0);
  fillchar(r,sizeof(r),0);
  fillchar(lx,sizeof(lx),0);
  fillchar(rx,sizeof(rx),0);
  r[1]:=a[1].y+a[1].r;
  for i:=2 to n do
    r[i]:=max(a[i].y+a[i].r,r[i-1]);
  l[n]:=a[n].y-a[n].r;
  for i:=n-1 downto 1 do
    l[i]:=min(a[i].y-a[i].r,l[i+1]);
  lx[1].up:=a[1].x+a[1].r;
  lx[1].low:=a[1].x-a[1].r;
  for i:=2 to n do
  begin
    lx[i].up:=max(a[i].x+a[i].r,lx[i-1].up);
    lx[i].low:=min(a[i].x-a[i].r,lx[i-1].low);
  end;
  rx[n].up:=a[n].x+a[n].r;
  rx[n].low:=a[n].x-a[n].r;
  for i:=n-1 downto 1 do
  begin
    rx[i].up:=max(a[i].x+a[i].r,rx[i+1].up);
    rx[i].low:=min(a[i].x-a[i].r,rx[i+1].low);
  end;
  for i:=1 to n-1 do
  if r[i]<l[i+1] then
  begin
    x1:=max(r[i]-l[1],100);
    y1:=max(lx[i].up-lx[i].low,100);
    x2:=max(r[n]-l[i+1],100);
    y2:=max(rx[i+1].up-rx[i+1].low,100);
    s:=x1*y1+x2*y2;
    if s<ans then ans:=s;
  end;
  writeln(ans:0:0);
end.

program ex;
type xx=record
     l,r,b,t:longint;
     end;
var a:array[1..1000] of xx;
    bb,tt,rr,ll,b1,t1,r1,l1:array[1..1000] of longint;
    c:xx;
    p1,q1,p2,q2,s,i,j,n,r,x,y,maxx,minx,maxy,miny:longint;

begin
  readln(n);
  fillchar(a,sizeof(a),0);
  maxx:=-maxint; maxy:=-maxint;
  minx:=maxint; miny:=maxint;
  for i:=1 to n do
  begin
    readln(r,x,y);
    a[i].l:=x-r; a[i].r:=x+r;
    a[i].t:=y+r; a[i].b:=y-r;
    if a[i].l<minx then minx:=a[i].l;
    if a[i].r>maxx then maxx:=a[i].r;
    if a[i].t>maxy then maxy:=a[i].t;
    if a[i].b<miny then miny:=a[i].b;
  end;
  p1:=maxx-minx;
  q1:=maxy-miny;
  if p1<100 then p1:=100; if q1<100 then q1:=100;
  s:=p1*q1;

  for i:=1 to n-1 do
    for j:=i+1 to n do
    if a[i].l>a[j].l then
    begin
      c:=a[i]; a[i]:=a[j]; a[j]:=c;
    end;
  bb[1]:=a[1].b; tt[1]:=a[1].t; rr[1]:=a[1].r;
  for i:=2 to n do
  begin
    if a[i].b<bb[i-1] then bb[i]:=a[i].b else bb[i]:=bb[i-1];
    if a[i].t>tt[i-1] then tt[i]:=a[i].t else tt[i]:=tt[i-1];
    if a[i].r>rr[i-1] then rr[i]:=a[i].r else rr[i]:=rr[i-1];
  end;
  b1[n]:=a[n].b; t1[n]:=a[n].t;
  for i:=n-1 downto 1 do
  begin
    if a[i].b<b1[i+1] then b1[i]:=a[i].b else b1[i]:=b1[i+1];
    if a[i].t>t1[i+1] then t1[i]:=a[i].t else t1[i]:=t1[i+1];
  end;
  for i:=1 to n-1 do
    if a[i+1].l>rr[i] then
    begin
      p1:=rr[i]-a[1].l;
      q1:=tt[i]-bb[i];
      p2:=rr[n]-a[i+1].l;
      q2:=t1[i+1]-b1[i+1];
      if p1<100 then p1:=100; if p2<100 then p2:=100;
      if q1<100 then q1:=100; if q2<100 then q2:=100;
      if p1*q1+p2*q2<s then s:=p1*q1+p2*q2;
    end;

  for i:=1 to n-1 do
    for j:=i+1 to n do
    if a[i].b>a[j].b then
    begin
      c:=a[i]; a[i]:=a[j]; a[j]:=c;
    end;
  ll[1]:=a[1].l; tt[1]:=a[1].t; rr[1]:=a[1].r;
  for i:=2 to n do
  begin
    if a[i].l<ll[i-1] then ll[i]:=a[i].l else ll[i]:=ll[i-1];
    if a[i].t>tt[i-1] then tt[i]:=a[i].t else tt[i]:=tt[i-1];
    if a[i].r>rr[i-1] then rr[i]:=a[i].r else rr[i]:=rr[i-1];
  end;
  l1[n]:=a[n].l; r1[n]:=a[n].r;
  for i:=n-1 downto 1 do
  begin
    if a[i].l<l1[i+1] then l1[i]:=a[i].l else l1[i]:=l1[i+1];
    if a[i].r>r1[i+1] then r1[i]:=a[i].r else r1[i]:=r1[i+1];
  end;
  for i:=1 to n-1 do
    if a[i+1].b>tt[i] then
    begin
      p1:=tt[i]-a[1].b;
      q1:=rr[i]-ll[i];
      p2:=tt[n]-a[i+1].b;
      q2:=r1[i+1]-l1[i+1];
      if p1<100 then p1:=100; if p2<100 then p2:=100;
      if q1<100 then q1:=100; if q2<100 then q2:=100;
      if p1*q1+p2*q2<s then s:=p1*q1+p2*q2;
    end;
  writeln(s);
end.

#include <stdio.h>
#include <string.h>

struct Tr{
    int r,x,y,lt,rt,up,dn;
};

Tr    p[1001];
long  s[1001],b[1001],s1[1001],b1[1001];
long  n,min,l,r,u,d,t1,t2,t3,tt;


void sort1(const int ll,int rr)
{
     long i,j;
     Tr xx,tt;

     i=ll; j=rr; xx=p[(ll+rr)/2];
     do
     {
         while ((p[i].lt<xx.lt) || (p[i].lt==xx.lt && p
[i].rt<xx.rt)) i++;
         while ((xx.lt<p[j].lt) || (xx.lt==p[j].lt && xx.rt<p
[j].rt)) j--;
         if (i<=j){
              tt=p[i]; p[i]=p[j]; p[j]=tt;
              i++; j--;
         }
     }while (i<=j);

     if (ll<j) sort1(ll,j);
     if (i<rr) sort1(i,rr);

}

void sort2(const int ll,int rr)
{
     long i,j;
     Tr xx,tt;

     i=ll; j=rr; xx=p[(ll+rr)/2];
     do
     {
         while ((p[i].dn<xx.dn) || (p[i].dn==xx.dn && p
[i].up<xx.up)) i++;
         while ((xx.dn<p[j].dn) || (xx.dn==p[j].dn && xx.up<p
[j].up)) j--;
         if (i<=j){
              tt=p[i]; p[i]=p[j]; p[j]=tt;
              i++; j--;
         }
     }while (i<=j);

     if (ll<j) sort2(ll,j);
     if (i<rr) sort2(i,rr);

}

long calc(long t1,long t2)
{
    if (t1<100) t1=100;
    if (t2<100) t2=100;
    return t1*t2;
}

void main()
{
    int i;

    scanf("%d",&n);
    l = 20000; r = -10000;
    d = 20000; u = -10000;
    for (i=1;i<=n;i++){
        scanf("%d%d%d",&p[i].r,&p[i].x,&p[i].y);
        p[i].lt=p[i].x-p[i].r;
        p[i].rt=p[i].x+p[i].r;
        p[i].up=p[i].y+p[i].r;
        p[i].dn=p[i].y-p[i].r;
        if (p[i].lt<l) l=p[i].lt;
        if (p[i].rt>r) r=p[i].rt;
        if (p[i].dn<d) d=p[i].dn;
        if (p[i].up>u) u=p[i].up;
    }
    t1 = r-l;
    t2 = u-d;
    min = calc(t1,t2);

    sort1(1,n);
    s[1]=p[1].dn; b[1]=p[1].up;
    tt = 0;
    for (i=2;i<=n;i++){
        if (p[i].dn<s[i-1]) s[i]=p[i].dn; else s[i]=s[i-1];
        if (p[i].up>b[i-1]) b[i]=p[i].up; else b[i]=b[i-1];
        if (p[i].rt>tt) tt=p[i].rt;
    }
    s1[n]=p[n].dn; b1[n]=p[n].up;
    for (i=n-1;i>=1;i--){
        if (p[i].dn<s1[i+1]) s1[i]=p[i].dn; else s1[i]=s1[i+1];
        if (p[i].up>b1[i+1]) b1[i]=p[i].up; else b1[i]=b1
[i+1];
    }
    for (i=1;i<n;i++)
        if (p[i].rt<=p[i+1].lt){
            t1 = p[i].rt-p[1].lt;
            t2 = b[i]-s[i];
            t3 = calc (t1,t2);
            t1 = tt-p[i+1].lt;
            t2 = b1[i+1]-s1[i+1];
            t3 = t3 + calc (t1,t2);
            if (t3<min) min=t3;
        }

    sort2(1,n);
    s[1]=p[1].lt; b[1]=p[1].rt;
    tt=0;
    for (i=2;i<=n;i++){
        if (p[i].lt<s[i-1]) s[i]=p[i].lt; else s[i]=s[i-1];
        if (p[i].rt>b[i-1]) b[i]=p[i].rt; else b[i]=b[i-1];
        if (p[i].up>tt) tt=p[i].up;
    }
    s1[n]=p[n].lt; b1[n]=p[n].rt;
    for (i=n-1;i>=1;i--){
        if (p[i].lt<s1[i+1]) s1[i]=p[i].lt; else s1[i]=s1[i+1];
        if (p[i].rt>b1[i+1]) b1[i]=p[i].rt; else b1[i]=b1
[i+1];
    }
    for (i=1;i<n;i++)
        if (p[i].up<=p[i+1].dn){
            t1 = p[i].up-p[1].dn;
            t2 = b[i]-s[i];
            t3 = calc (t1,t2);
            t1 = tt-p[i+1].dn;
            t2 = b1[i+1]-s1[i+1];
            t3 = t3 + calc (t1,t2);
            if (t3<min) min=t3;
        }

    printf("%d\n",min);
}