Обсуждение @ 1245. Картины @ Timus Online Judge

I think my program is right, but it get WA!

Послано Grebnov Ilya[ISPU] 12 мар 2003 01:02

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

A test for you (+)

Послано Dmitry 'Diman_YES' Kovalioff 13 мар 2003 08:41

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 :)

Re: A test for you (+)

Послано Grebnov Ilya[ISPU] 14 мар 2003 11:54

> 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

Re: A test for you (+)

Послано Popovich Antony 24 мар 2003 16:28

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...

Re: A test for you (+)

Послано Yu YuanMing 13 сен 2004 20:40

My AC program output 620000

take care that one spot may cover another...

Re: A test for you (+)

Послано Edric Mao 14 окт 2011 13:40

Thax

Обсуждение задачи 1245. Картины