Maybe this: the minimal length of the sides of the map is 100 or that it could be one map. The spots (or pictures) maybe have points with negative coordinates? Пятна (или картины) могут иметь точки с отрицательными координатами? Edited by author 14.05.2007 16:56 No, they haven't. You are wrong. All spots must have integer positive coordinates of centers only. For example the spot 100 1 1 is valid. And it is covered by a picture with angle coordinates (-99,-99)-(101,101). Please, write in the statement that coordinates of pictures can be negative. 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 Try this: 5 200 200 400 100 400 600 100 500 300 100 900 100 200 900 600 The answer should be 620000, but your program writes 680000. P.S. Using GoTo is a new word in the technics of programming :) > Try this: > > 5 > 200 200 400 > 100 400 600 > 100 500 300 > 100 900 100 > 200 900 600 > > The answer should be 620000, but your program writes 680000. New version writes 620000, but it still Wrong! 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 := -Big I think, that right answer for this test is 540000. Please, explain me, why it's wrong. My program gives 540000, and I have drew it on a paper. I think, that it's right... My program gives WA... My AC program output 620000
take care that one spot may cover another... 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). because "and the minimally possible size of a picture in each of the dimensions is 100 millimeters" :-) 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); } |
|