Задача B. Разрезание многогранника ≡
| Автор: | А. Баранов | Ограничение времени: | 1 сек | |
| Входной файл: | input.txt | Ограничение памяти: | 512 Мб | |
| Выходной файл: | output.txt | |||
| Максимальный балл: | 100 |
Условие
Пусть имеется выпуклый многогранник и две плоскости, каждая из которых задается ортогональным к ней вектором U⃗k.
Известно, что плоскость можно сдвигать относительно начала координат
путем смещения всех составляющих ее точек на вектор S⃗k = tk ⋅ U⃗k|U⃗k|, где tk — произвольный скалярный параметр.
Требуется расположить указанные плоскости таким образом,
чтобы они разбивали исходный многогранник ровно на три части одинакового объема.
Формат входного файла
В начале входного файла "input.txt" записано число N, за которым следует 3 × N вещественных координат вершин.
Далее указано число M, за которым следует M граней, записанных в следующем виде.
Вначале для каждой грани указано число ее вершин, за которым следуют их индексы,
перечисленные в порядке их обхода для получения ограничивающего цикла грани.
При этом полагается, что нумерация вершин начинается с нуля.
В окончании входного файла записаны компоненты векторов, задающих плоскости
(сначала для 1-го, а затем для 2-го).
Формат выходного файла
Если решение существует, в выходной файл "output.txt" следует вывести число 1
и пару вещественных параметров t1 и t2, указанных с точностью не менее 5-го знака после запятой.
В противном случае, выходной файл должен содержать единственное число 0.
Ограничения
Исходный многогранник является невырожденным (имеет ненулевой объем).
Все грани представляют собой выпуклые многоугольники.
Координаты всех вершин по модулю не превосходят 10.
Число вершин и граней не превосходит 100.
Гарантируется, что в пределах заданной
точности ответ может быть
получен однозначно.
Примеры тестов
| № | Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|---|---|
| 1 | |
|