Спасательный маяк
Пытаясь избежать некоторых старых и не очень довольных кредиторов, Хан Соло разбил "Тысячелетний сокол" на ледяной планете Хот. Теперь ему нужно наладить аварийный сигнал, чтобы его спасли, прежде чем его друг Вуки превратится в меховую сосульку или решит съесть шашлык из Хана. Можешь помочь ему?
Хан сумел спасти очень яркий лазер, который можно увидеть за световые годы, и подумал, что это будет хорошим сигналом. Проблема в том, что если он просто направит его прямо в небо, будет минимальный шанс, что кто-то окажется на пути света и увидит его. Тем временем Чубакка играл с кучей сильно отражающих, многогранных кристаллов, которые он нашел в пещере поблизости. Затем, в момент вдохновения, Хан понял, что он может собрать спасательный маяк, направив свет на кристалл, грани которого, в свою очередь, отразят свет в небо в множестве направлений!
Рисунок 1: Упрощенная, двумерная иллюстрация спасательного маяка Хана.
Единственная оставшаяся проблема заключается в выборе кристалла для использования в качестве отражателя света. Каждый из отражающих кристаллов имеет форму выпуклого многогранника, поверхность которого состоит исключительно из идеально треугольных граней, и может быть установлен в маяке в любом направлении. Конечно, лучший кристалл для использования — это тот, который будет отражать лазерный луч (состоящий из параллельных световых лучей из одного направления) обратно в наибольшее количество направлений. Другими словами, вы можете считать отражающую способность кристалла просто количеством граней на нем, которые можно увидеть из любого одного направления обзора, так как именно эти грани могут быть одновременно освещены лазерным лучом. Имея описание геометрии каждого из кристаллов, можете ли вы вычислить наибольшее количество направлений, в которых кристалл может отразить лазер?
Входные данные
Входные данные будут состоять из геометрических описаний кристаллов из коллекции Чубакки. Описание каждого кристалла начинается с целого числа n (4 ≤ n ≤ 2000), количества граней на кристалле, на одной строке, за которой следуют n строк, описывающих грани. Каждая грань описывается 9 целыми числами, x_1 y_1 z_1 x_2 y_2 z_2 x_3 y_3 z_3, где точки (x_1, y_1, z_1), (x_2, y_2, z_2) и (x_3, y_3, z_3) в трехмерном пространстве образуют вершины треугольной грани в порядке против часовой стрелки (в правосторонней системе координат) при просмотре снаружи. Все координаты находятся в диапазоне -2000 ≤ x_i, y_i, z_i ≤ 2000, ни одна грань не имеет площади поверхности более 200000, и ни две грани не смотрят в одном направлении. Вы можете ожидать, что когда все грани каждого кристалла собраны, они образуют замкнутый выпуклый многогранник. Наконец, ни один кристалл не будет иметь структуры с какой-либо вырожденностью, которая могла бы вызвать двусмысленность в отношении того, сколько граней может быть освещено лазером. Другими словами, не должно иметь значения, считаете ли вы грани, параллельные лазерному лучу, способными отражать луч или нет - тестовые данные были сконструированы таким образом, что любое толкование дало бы одинаковый ответ. Другими словами, не должно иметь значения, считаете ли вы грани, параллельные лазерному лучу, способными отражать свет или нет. Ввод завершается строкой, содержащей число 0 (не обрабатывайте это как тестовый случай).
Выходные данные
Для каждого кристалла выведите на одной строке целое число m: наибольшее количество направлений, в которых кристалл может одновременно отражать лазерный луч.