Puste prostopadłościany
Limit pamięci: 32 MB
Prostopadłościan nazwiemy regularnym, gdy:
- jednym z jego wierzchołków jest punkt o współrzędnych ,
- 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ż .
Dany jest zbiór punktów przestrzeni, których wszystkie współrzędne są całkowite i należą do przedziału . Szukamy prostopadłościanu regularnego o maksymalnej objętości, który w swoim wnętrzu nie zawiera żadnego punktu ze zbioru . 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 ze standardowego wejścia współrzędne punktów ze zbioru ,
- wyznaczy jeden z prostopadłościanów regularnych o maksymalnej objętości, nie zawierający w swoim wnętrzu punktów ze zbioru ,
- wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu standardowego wejścia znajduje się jedna całkowita nieujemna liczba , , będąca liczbą elementów zbioru .
W kolejnych wierszach wejścia znajdują się trójki liczb całkowitych z przedziału będące współrzędnymi (odpowiednio , i ) punktów ze zbioru . Liczby w wierszu pooddzielane są pojedynczymi odstępami.
Wyjście
W jednym wierszu standardowego wyjścia powinny znaleźć się trzy liczby całkowite oddzielone pojedynczymi odstępami, będące współrzędnymi (odpowiednio , i ) tego wierzchołka znalezionego prostopadłościanu regularnego, który ma wszystkie współrzędne dodatnie.
Przykład
Dla danych wejściowych:
4
3 3 300000
2 200000 5
90000 3 2000
2 2 1000
poprawną odpowiedzią jest:
1000000 200000 1000
Autor zadania: Bogdan S. Chlebus.