Задача №115278. Строительство пирамиды
Как известно, египетские пирамиды — одни из самых известных чудес света. Они были построены пришельцами в давние-давние времена. Пришелец Ар'глх, каждый день пролетая мимо Земли на работу и обратно, часто делает остановку, чтобы полюбоваться этими величественными сооружениями и найти вдохновение.
Видите ли, Ар'глх — архитектор и проектирует свою собственную пирамиду. К счастью, с новыми технологиями для постройки пирамиды ему не понадобятся ни огромные каменные блоки, ни труд множества египетских рабочих, но это все еще не значит, что его задача проста.
За последние столетия Ар'глх собрал \(n\) карбоновых треугольных граней, \(i\)-я из которых имеет стороны длиной \(a_i\), \(b_i\) и \(c_i\), соответственно. Он хочет выбрать четыре грани и собрать их них пирамиду в форме невырожденного тетраэдра. Разумеется, грани должны точно прилегать друг к другу без деформаций и пропусков и не должны выступать за тетраэдр. Объем тетраэдра должен быть строго положительным.
Помогите инопланетному архитектору определить, какие четыре грани он может выбрать из имеющегося у него набора, чтобы собрать из них пирамиду в форме тетраэдра.
В первой строке дано целое число \(n\) — количество треугольных граней в наличии у Ар'глха (\(4 \leq n \leq 1500\))
В \(i\)-й из следующих \(n\) строк перечислены три целых числа \(a_i\), \(b_i\) и \(c_i\) — длины сторон \(i\)-й грани (\(1 \leq a_i, b_i, c_i \leq 10\,000\), гарантируется, что каждая грань является корректным треугольником, то есть \(a_i + b_i > c_i\), \(a_i + c_i > b_i\), \(b_i + c_i > a_i\)).
Если Ар'глх сможет выбрать четыре грани, из которых можно собрать тетраэдр, выведите в первой строке слово « Yes ». Во второй строке выведите четыре различных целых числа от \(1\) до \(n\) — номера граней, которые можно использовать для строительства. Если возможных ответов несколько, выведите любой из них.
Иначе выведите слово « No ».
7 3 3 3 3 4 5 4 5 6 3 4 3 3 3 5 6 5 7 3 5 5
Yes 2 4 5 7
5 2 3 4 3 4 5 4 5 6 5 6 7 6 7 8
No
4 2 3 4 3 4 2 3 2 4 4 2 3
No