Show all threads Hide all threads Show all messages Hide all messages | I got WA#3! Please give me some hints about this test. | {AESC USU} Evgeny Kurpilyanskij | 1245. Pictures | 24 Sep 2012 18:16 | 7 | 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 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. | If you've get WA#9 try this: | Fly [Yaroslavl_SU] | 1245. Pictures | 14 Oct 2011 13:46 | 2 | 2 8 0 0 8 100 0 Answer: 11600 | I think my program is right, but it get WA! | Grebnov Ilya[ISPU] | 1245. Pictures | 14 Oct 2011 13:40 | 6 | 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... | WA#3 | hoan | 1245. Pictures | 30 Nov 2010 22:16 | 1 | WA#3 hoan 30 Nov 2010 22:16 in this test ther is only one pictures need, like this: input: 1 100 0 0 output: 40000 GOOD LUCK!!! | Here some tests... They saved me... | KIEV_lyceum_№145 (Grinenko,Kalugin,Ryjouk) | 1245. Pictures | 30 Nov 2010 22:15 | 2 | >2 0 0 8 2 2 6 My output: 10000 3 745 852 22 49 235 549 856 460 11 My output: 3412016 | C++ Compilation error | Hatred | 1245. Pictures | 12 Feb 2010 16:40 | 1 | 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. | Mistake in statement | Fyodor Menshikov | 1245. Pictures | 12 May 2009 14:00 | 2 | приведение, живущее в доме -> привидение, живущее в доме | test16 | sich_off (ONPU) | 1245. Pictures | 26 Feb 2009 23:35 | 1 | test16 sich_off (ONPU) 26 Feb 2009 23:35 it appeares when you count area wrongly for one spot with r > 50 | why answer for test from statement is 40000? | Rumter (3) | 1245. Pictures | 13 Nov 2008 19:55 | 2 | 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" :-) | To admin: Incorrect test 7 | Beksinski | 1245. Pictures | 21 Mar 2008 02:09 | 2 | 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 | Why WA #8 ? | xiao | 1245. Pictures | 27 Apr 2006 20:29 | 1 | | Test 2 | TestT | 1245. Pictures | 23 Feb 2005 13:00 | 1 | Test 2 TestT 23 Feb 2005 13:00 2 50 50 50 100 200 100 ans = 50000 | Problem 1245 was rejudged | Vladimir Yakovlev (USU) | 1245. Pictures | 24 Oct 2004 02:29 | 1 | | Are there any solutions faster than O(nlogn)? | Yaroslavtsev Grigory | 1245. Pictures | 17 Sep 2004 01:40 | 1 | | Coordinates can be negative! | Stupnikov Pavel | 1245. Pictures | 15 Sep 2004 21:41 | 2 | Task says that "spot is described by three positive integers". But it is only difference between my AC and WA programs! (test #8) | Who can give me some testdatas?I got WA:( | awts | 1245. Pictures | 8 Jun 2003 18:14 | 1 | | why my codes got WA, who can give me some testdata please? | BShell | 1245. Pictures | 16 May 2003 15:58 | 1 | 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. | Can the spots overlay?(-) | zhangqi | 1245. Pictures | 11 May 2003 21:26 | 2 | Yes (-) Dmitry 'Diman_YES' Kovalioff 11 May 2003 21:26 | CAN ANYONE TELL ME WHAT'S WRONG WITH MY PROGRAM?? | beiyz | 1245. Pictures | 21 Mar 2003 18:28 | 1 | 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. | what's wrong with this code?(+) | James | 1245. Pictures | 16 Mar 2003 20:00 | 1 | #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); } |
|
|