Polish version    English version  
  O olimpiadzie -> Zadania -> VI OI 1998/1999


 Aktualności
 O olimpiadzie
O olimpiadzie
Zadania
I OI 1993/1994
II OI 1994/1995
III OI 1995/1996
IV OI 1996/1997
V OI 1997/1998
VI OI 1998/1999
VII OI 1999/2000
VIII OI 2000/2001
IX OI 2001/2002
X OI 2002/2003
XI OI 2003/2004
XII OI 2004/2005
XIII OI 2005/2006
XIV OI 2006/2007
XV OI 2007/2008
Archiwum zadań
Ankieta OI
 Komitety
 XVIII OI 2010/2011
 Historia OI
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
VI Olimpiada Informatyczna 1998/99

Zadanie: PUS
Autor: Bogdan S. Chlebus
Puste prostopadłościany

Zawody I stopnia
Plik źródłowy: PUS.??? (np. pas, c, cpp)
Plik wykonywalny: PUS.exe
Plik wejściowy: PUS.in
Plik wyjściowy: PUS.out

Prostopadłościan nazwiemy regularnym, gdy:

  • jednym z jego wierzchołków jest punkt o współrzędnych (0,0,0),
  • krawędzie wychodzące z tego wierzchołka leżą na dodatnich półosiach układu współrzędnych,
  • krawędzie te mają długości nie większe niż 106

Dany jest zbiór A punktów przestrzeni, których wszystkie współrzędne są całkowite i należą do przedziału [1..106]. Szukamy prostopadłościanu regularnego o maksymalnej objętości, który w swoim wnętrzu nie zawiera żadnego punktu ze zbioru A. Punkt należy do wnętrza prostopadłościanu jeżeli jest punktem prostopadłościanu, ale nie jego ściany.

Zadanie

Napisz program, który:

  • wczyta z pliku tekstowego PUS.IN współrzędne punktów ze zbioru A,
  • wyznaczy jeden z prostopadłościanów regularnych o maksymalnej objętości, nie zawierający w swoim wnętrzu punktów ze zbioru A,
  • zapisze wynik do pliku tekstowego PUS.OUT

Wejście

W pierwszym wierszu pliku wejściowego PUS.IN znajduje się jedna całkowita nieujemna liczba n, n <= 5000, będąca liczbą elementów zbioru A.
W kolejnych n wierszach pliku PUS.IN znajdują się trójki liczb całkowitych z przedziału [1..106] będące współrzędnymi (odpowiednio x, y i z) punktów ze zbioru A. Liczby w wierszu pooddzielane są pojedynczymi odstępami.

Wyjście

W jednym wierszu pliku wejściowego PUS.OUT powinny znaleźć się trzy liczby całkowite oddzielone pojedynczymi odstępami, będące współrzędnymi (odpowiednio x, y i z) tego wierzchołka znalezionego prostopadłościanu regularnego, który ma wszystkie współrzędne dodatnie.

Przykład

Dla pliku wejściowego PUS.IN:

4
3 3 300000
2 200000 5
90000 3 2000
2 2 1000

poprawną odpowiedzią jest plik tekstowy PUS.OUT:

1000000 200000 1000

Twój program powinien szukać pliku PUS.IN w katalogu bieżącym i tworzyć plik PUS.OUT również w bieżącym katalogu. Plik zawierający napisany przez Ciebie program w postaci źródłowej powinien mieć nazwę PUS.???, gdzie zamiast ??? należy wpisać co najwyżej trzyliterowy skrót nazwy użytego języka programowania. Ten sam program w postaci wykonywalnej powinien być zapisany w pliku PUS.EXE




Wersja do druku