[Pascal] Minimalny obwód prostokąta zawierającego punkty

wozszym
Użytkownik
Użytkownik
Posty: 15
Rejestracja: 25 kwie 2009, o 16:09
Płeć: Mężczyzna
Podziękował: 2 razy

[Pascal] Minimalny obwód prostokąta zawierającego punkty

Post autor: wozszym »

Mam program, który wczytuje ilość ptk. na płaszczyźnie, współrzędne w wypisuje minimalny obwód prostokąta o bokach równoległych do osi, zawierającego te punkty. działa on jednak wolno i zabiera dużo pamięci. Jak mogę go ulepszyć?

Kod: Zaznacz cały

program prostokat;

var tab: array[1..200000] of Longint;
tabb: array[1..200000] of Longint;
n,a,i,j,k,r,p,w,z,x: Longint;

begin

for i:=1 to 200000 do
tab[i]:=0;
for i:=1 to 200000 do
tabb[i]:=0;

Read(n);
for i:=1 to 2*n do
 begin
 Read(a);
 if a<0 then a:=(-1)*a;
 if i mod 2=1 then tab[i]:=a
 else tabb[i]:=a;
 end;
r:=0;
for i:=1 to 2*n do
 for j:=1 to 2*n do
 begin
 if tab[i]-tab[j]<0 then r:=(tab[j]-tab[i])
 else r:=(tab[i]-tab[j]);
 end;
for i:=1 to 2*n do
 for j:=1 to 2*n do
 begin
  w:=0;
  if tab[i]-tab[j]<0 then w:=(tab[j]-tab[i])
 else w:=(tab[i]-tab[j]);

  if w>r then r:=w;
  end;

z:=0;
for i:=1 to 2*n do
 for j:=1 to 2*n do
 begin
 if tabb[i]-tabb[j]<0 then z:=(tabb[j]-tabb[i])
 else z:=(tabb[i]-tabb[j]);
 end;
for i:=1 to 2*n do
 for j:=1 to 2*n do
 begin
  x:=0;
  if tabb[i]-tabb[j]<0 then x:=(tabb[j]-tabb[i])
 else x:=(tabb[i]-tabb[j]);

  if x>z then z:=x;
 end;

Write(2*(r-1)+2*(z-1));


end.

Ponadto próbowałem ulepszyć samą część wyszukiwania maksymalnej różnicy, ale po zmianach(poniżej) program nie chce działać

Kod: Zaznacz cały

program maksymalna_roznica;

var tab: array[1..500000] of Longint;
r,i,j,n,w: Longint;

begin
Read(n);
r:=0;
for i:=1 to n do Read(tab[i]);
for i:=1 to n do
 for j:=1 to n do
 begin
 w:=0;
 if (tab[i]-tab[j])<0 then w:=(tab[j]-tab[i])
 else w:=(tab[i]-tab[j]);
 if w>r then r:=w;
 end;

Write(r);

end.
Ostatnio zmieniony 20 lip 2012, o 16:15 przez Afish, łącznie zmieniany 1 raz.
Powód: Staraj się lepiej dobierać nazwy tematów, tak by wskazywały o czym jest treść zadania.
Afish
Moderator
Moderator
Posty: 2828
Rejestracja: 15 cze 2008, o 15:45
Płeć: Mężczyzna
Lokalizacja: Seattle, WA
Podziękował: 3 razy
Pomógł: 356 razy

[Pascal] Minimalny obwód prostokąta zawierającego punkty

Post autor: Afish »

Nie wystarczy po prostu znaleźć graniczne współrzędne? Przejedź po wszystkich punktach i znajdź maksymalną oraz minimalną wartość współrzędnej \(\displaystyle{ x}\), oraz analogiczne wartości dla współrzędnej \(\displaystyle{ y}\).
ODPOWIEDZ