Задача №115175. Путёвка на Острова Кука
Боб — туристический агент. Его задача — продавать туристам путёвки на Острова Кука. Вдохновившись успехом Биба — туристического агента с Бермудских Островов, Боб решил распространить информацию о мистических треугольниках Кука !
Острова Кука состоят из \(3n\) небольших островов. Острова настолько маленькие, что каждый остров может быть представлен на карте одной точкой \((x, y)\) с целыми положительными координатами.
Боб хочет разбить все \(3n\) островов на \(n\) групп по \(3\) острова так, чтобы координаты трёх островов в каждой из групп образовывали невырожденный треугольник. Напомним, что треугольник называется невырожденным, если все его углы строго больше нуля и меньше \(180^{\circ}\).
Помогите Бобу найти любое подходящее разбиение островов на треугольники, чтобы продать все путёвки на Острова Кука! Если подходящего разбиения не существует, вы также должны сообщить об этом.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число \(t\) (\(1 \le t \le 10^5\)) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число \(n\) (\(1 \le n \le 10^5\)) — количество треугольников, которые нужно сформировать из \(3n\) островов.
В каждой из следующих \(3n\) строк находятся два целых числа \(x, y\) (\(1 \le x, y, \le 10^9\)) — координаты очередного острова. Гарантируется, что координаты всех островов попарно различны, другими словами, никакие два острова не находятся в одной и той же точке.
Гарантируется, что сумма значений \(n\) по всем наборам входных данных не превосходит \(10^5\).
Для каждого набора входных данных, если ответа не существует, в единственной строке выведите «No» . Иначе, выведите «Yes» , а затем, в последующих \(n\) строках, индексы островов образующих очередной треугольник. Острова нумеруются с \(1\) в том же порядке, как и во входных данных. Если ответов несколько, вы можете вывести любой из них.
Вы можете выводить «Yes» и «No» в любом регистре.
4 2 1 1 2 2 3 3 4 4 4 5 2 4 1 9 3 3 1 6 2 3 7 8 8 10 9 12 10 14 10 10 16 14 19 16 1 12 28 18 5 100000000 1000000000 200000000 1000000000 300000000 1000000000 400000000 1000000000 500000000 1000000000 600000000 1000000000 700000000 1000000000 800000000 1000000000 900000000 1000000000 1000000000 1000000000 1 1 2 2 3 3 4 4 5 5
Yes 5 4 3 6 2 1 No Yes 4 5 9 3 8 7 6 2 1 Yes 11 10 9 12 8 7 13 6 5 14 4 3 15 2 1