VI Olimpiada Informatyczna 1998/99
|
Zadanie: PUS
|
Autor: Bogdan S. Chlebus
|
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:
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.
Napisz program, który:
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.
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.
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