Fivt_3/task-B/25.11.2017 (2'st test)

#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
#include <cassert>
#include <iterator>


struct Point {
	int  x;
	int  y;
	int  z;
	int number;
	Point(int _x, int _y, int _z, int _number = 0):
			x(_x),
			y(_y),
			z(_z),
			number(_number)
	{
	}

	Point(const Point& other) {
		x = other.x;
		y = other.y;
		z = other.z;
		number = other.number;
	}
	bool operator==(const Point& other) const;
	bool operator!=(const Point& other) const;
	Point operator-(const Point& other) const;
	double operator^(int p) const;
	double operator*(const Point& other) const;
	double GetModule() const;
	void Print() const;
};


bool Point::operator==(const Point &other) const{
	return (this->x == other.x && this->y == other.y && this->z == other.z);
}


bool Point::operator!=(const Point &other) const{
	return (this->x != other.x || this->y != other.y || this->z != other.z);
}

Point Point::operator-(const Point& other) const{
	return {this->x - other.x, this->y - other.y, this->z - other.z};
}


double Point::operator^(int p) const{
	return std::pow(this->x,p) + std::pow(this->y,p) + std::pow(this->z,p);
}


double Point::operator*(const Point &other) const{
	return (this->x*other.x + this->y*other.y + this->z*other.z);
}

Point OtherPointFromSet(const Point& this_point, const std::vector<Point> &points) {
	assert(!points.empty());
	for(const auto& point: points ) {
		if (point != this_point) {
			return point;
		}
	}
}

double Point::GetModule() const {
	return std::sqrt( this->x*this->x + this->y*this->y + this->z*this->z );
}


void Point::Print() const {
	std::cout<<this->x<<' '<<this->y<<' '<<this->z;
	std::cout<<'\n';
}


Point VectorMultiplication(const Point& p1, const Point& p2) {
	return {p1.y*p2.z - p1.z*p2.y, - (p1.x*p2.z - p1.z*p2.x ), p1.x*p2.y - p1.y*p2.x};
}

double Distance(const Point& p1, const Point& p2) {
	return std::sqrt( (p1-p2)^2 );
}


double OzAngle(const Point& p1, const Point& p2) {
	Point Oz (0,0,1);
	Point p12  = p2 - p1;
	double t = (p12*Oz)/std::sqrt((p12*p12)*(Oz*Oz));
	if (t < -1) {
		t = -1;
	}
	else if(t > 1) {
		t = 1;
	}
	double acos = std::acos(t);
	return acos;
}


Point MostBottom(const std::vector<Point>& points) {
	Point point_min = points[0];
	for (const auto& point: points) {
		if (point.z < point_min.z) {
			point_min = point;
		}
	}
	return point_min;
}


struct Edge {
	Point p1;
	Point p2;
	Point forbidden_point;
	bool IsProcessed;
	Edge(const Point& _p1, const Point& _p2, const Point& _forbidden_point);
	Edge(const Edge& edge, const Point& _forbidden_point);
	Edge(const Edge& edge);
	Point PivotAroundEdge(const std::vector<Point> &points);
	bool operator==(const Edge& other) const;
};


Edge::Edge(const Point& _p1, const Point& _p2, const Point& _forbidden_point) :
		p1(_p1),
		p2(_p2),
		forbidden_point(_forbidden_point),
		IsProcessed(false)
{
}


Edge::Edge(const Edge& edge, const Point& _forbidden_point) :
	p1(edge.p1),
	p2(edge.p2),
	forbidden_point(_forbidden_point),
	IsProcessed(false)
{
}

Edge::Edge(const Edge &edge) :
	p1(edge.p1),
	p2(edge.p2),
	forbidden_point(edge.forbidden_point),
	IsProcessed(edge.IsProcessed)
{
}

bool Edge::operator==(const Edge& other) const{
	return (this->p1 == other.p1 && this->p2 == other.p2 ||
			this->p1 == other.p2 && this->p2 == other.p1);
}



double FindOutFaceD(double A, double B, double C, const Point& pivot) {
	return -( A*pivot.x + B*pivot.y + C*pivot.z );
}


struct Triangle {
	Edge edge12;
	Edge edge23;
	Edge edge31;
	Triangle(const Edge& edge, const Point& point);
	Triangle(const Edge& edge1, const Edge& edge2, const Edge& edge3);
	std::vector<Edge> GetEdges();
	Point GetExternalVector(const std::vector<Point>& points);
	std::vector<Point> GetPointsInProperOrder(const std::vector<Point> &points);
};

Triangle::Triangle(const Edge& edge, const Point& point) :
	edge12(edge, point),
	edge23(edge.p1, point, edge.p2),
	edge31(edge.p2, point, edge.p1)
{
}


Triangle::Triangle(const Edge& edge1, const Edge& edge2, const Edge& edge3) :
	edge12(edge1),
	edge23(edge2),
	edge31(edge3)
{
}


Point GetOtherPoint(const std::vector<Point>& triangles_points, const std::vector<Point> &points) {
	assert(triangles_points.size() == 3);
	for (const auto& point: points) {
		if ((point != triangles_points[1] && point != triangles_points[2])
			&& point != triangles_points[0]) {
			return point;
		}
	}
}


std::vector<Point> GetPointsOfTriangle(const Triangle& triangle) {
	std::vector<Point> points = { triangle.edge12.p1, triangle.edge12.p2, triangle.edge23.p1,
								  triangle.edge23.p2, triangle.edge31.p1, triangle.edge31.p2 };
	std::sort(points.begin(), points.end(), [](const Point& p1, const Point& p2){ return p1.number <= p2.number  ; });
	auto last = std::unique(points.begin(), points.end());
	points.erase(last, points.end());
	return points;
}


Point Triangle::GetExternalVector(const std::vector<Point>& points) { //O(1)
	Triangle this_triangle = *this;
	std::vector<Point> triangles_points = GetPointsOfTriangle(this_triangle);
	assert(triangles_points.size() == 3);
	Point v1 = triangles_points[1] - triangles_points[0];
	Point v2 = triangles_points[2] - triangles_points[0];
	Point vector_normal_1 = VectorMultiplication(v1,v2);
	Point vector_normal_2 = VectorMultiplication(v2,v1);

	double D_1 = FindOutFaceD(vector_normal_1.x, vector_normal_1.y, vector_normal_1.z, triangles_points[0]);
	double D_2 = FindOutFaceD(vector_normal_2.x, vector_normal_2.y, vector_normal_2.z, triangles_points[0]);

	Point other_point = GetOtherPoint(triangles_points, points); // проверяем только на одной точке

	if (vector_normal_1*other_point + D_1 < 0) { //приколюшка только для грани!!!
		return vector_normal_1;
	}
	else if (vector_normal_2*other_point + D_2 < 0) {
		return vector_normal_2;
	}
	else {
		std::cout<<"Can't Find External Vector for Triangle";
		exit(1);
	}
}



std::vector<Point> Triangle::GetPointsInProperOrder(const std::vector<Point> &points) {
	Triangle this_triangle = *this;
	std::vector<Point> triangle_points = GetPointsOfTriangle(this_triangle);
	std::vector<Point> proper_order_points;
	Point external_normal_vector = this->GetExternalVector(points);
	int iter_of_min = 0;																			//FIX!!!
	for (int i = 1; i < triangle_points.size(); ++i) {
		if (triangle_points[iter_of_min].number > triangle_points[i].number) {
			iter_of_min = i;
		}
	}
	std::swap(triangle_points[iter_of_min],triangle_points[0]);
	proper_order_points.push_back(triangle_points[0]);

	Point v1 = VectorMultiplication(triangle_points[1] - triangle_points[0],external_normal_vector);
	Point v2 = VectorMultiplication(triangle_points[2] - triangle_points[0],external_normal_vector);
	double D_1 = FindOutFaceD(v1.x , v1.y, v1.z, triangle_points[1]);
	double D_2 = FindOutFaceD(v2.x , v2.y, v2.z, triangle_points[2]);
	if ( v1*triangle_points[2] + D_1 < 0 ) {
		proper_order_points.push_back(triangle_points[1]);
		proper_order_points.push_back(triangle_points[2]);
	}
	else if ( v2*triangle_points[1] + D_2 < 0 ) {
		proper_order_points.push_back(triangle_points[2]);
		proper_order_points.push_back(triangle_points[1]);
	}
	else {
		std::cout<<"Can't find right order";
		exit(1);
	}
	return proper_order_points;
}


std::vector<Edge> Triangle::GetEdges() {
	return {edge12,edge23,edge31};
}


double AngleBetweenTriangles(const std::vector<Point>& points, Triangle& first, Triangle& second) {
	Point v1 = first.GetExternalVector(points);
	Point v2 = second.GetExternalVector(points);
	double angle = (v1 * v2)/(v1.GetModule() * v2.GetModule());
	return  angle;
}


bool IsFace(Triangle& triangle, const std::vector<Point>& points) { // how to do O(1)
	std::vector<Point> triangles_points = GetPointsOfTriangle(triangle);
	Point normal = triangle.GetExternalVector(points);

	double D_of_triangle = FindOutFaceD(normal.x, normal.y, normal.z, triangles_points[0]);
	std::vector<double> D_of_other_points;
	for (const auto& point: points) {
		if ( (point !=  triangles_points[1] && point !=  triangles_points[2]) && point !=  triangles_points[0]) {
			double D = FindOutFaceD(normal.x, normal.y, normal.z, point);
			D_of_other_points.push_back(D);
		}
	}
	double min_element = *std::min_element(D_of_other_points.begin(), D_of_other_points.end());
	double max_element = *std::max_element(D_of_other_points.begin(), D_of_other_points.end());
	bool result = (D_of_triangle < min_element ||
			D_of_triangle > max_element ) ;
	return result;
}



Edge FindEdgeOnHull(const std::vector<Point>& points) {
	Point p1 = MostBottom(points);
	Point p2 = OtherPointFromSet(p1, points);
	for (const auto& point: points) {
		if ( p1 != point && OzAngle(p1,point) >= OzAngle(p1,p2) ) {
			p2 = point;
		}
	}
	return {p1,p2,p1};
}

Triangle FindtTriangleOnHull(std::vector<Point>& points) { //O(n^2)
	Edge edge = FindEdgeOnHull(points);
	Point pivot = edge.PivotAroundEdge(points);
	edge.forbidden_point = pivot;
	return  {edge, pivot};
}


//Triangle FindNewTriangle(const std::vector<Point> &points, const Edge& edge) { // need O(n)
//	Point p1 = edge.p1;
//	Point p2 = edge.p2;
//	Point forbidden_point  = edge.forbidden_point;
//	Triangle based_triangle = Triangle(edge, forbidden_point);
//	std::vector<Point> triangle_points = GetPointsOfTriangle(based_triangle);
//	Point other_point = GetOtherPoint(triangle_points, points);
//	Triangle current_triangle = Triangle(edge, other_point);
//
//	for (const auto& point: points) { // need O(n)
//		if ((point != p1 && point != p2) && point != forbidden_point) {
//			Triangle new_triangle (edge, point);
//			if (AngleBetweenTriangles(points, based_triangle, new_triangle) >
//				AngleBetweenTriangles(points, based_triangle, current_triangle)) { // O(1)
//				current_triangle = new_triangle;
//			}
//		}
//	}
//	return current_triangle;
//}

Triangle FindNewTriangle(const std::vector<Point> &points, const Edge& edge) {

	Point p1 = edge.p1;
	Point p2 = edge.p2;
	Point p3 = edge.forbidden_point;
	std::vector<Point> triangle_points = {p1,p2,p3};

	Point rotate_vector (0,0,0);
	Point base_point (0,0,0);
	Point normal (0,0,0);

	Point p1p2 = p2 - p1;
	Point p2p1 = p1 - p2;
	Point norm_v1 = VectorMultiplication(p1p2,p3-p1);
	Point norm_v2 = VectorMultiplication(p2p1,p3-p2);
	Point other_point = GetOtherPoint(triangle_points, points);
	if (norm_v1*other_point + FindOutFaceD(norm_v1.x, norm_v1.y, norm_v1.z, p1) < 0) {
		rotate_vector = p1p2;
		base_point = p1;
		normal = norm_v1;
	}
	else if (norm_v2*other_point + FindOutFaceD(norm_v2.x, norm_v2.y, norm_v2.z, p1) < 0) {
		rotate_vector = p2p1;
		base_point = p2;
		normal = norm_v2;
	}
	else {
		std::cout<<" Can't find rotate vector for ";
		edge.p1.Print();
		edge.p2.Print();
		exit(1);
	}

	Point pivot = other_point;
	Point current_vector = VectorMultiplication(pivot - base_point, rotate_vector);

	for (const auto& point: points) { // need O(n)
		if ((point != p1 && point != p2) && point != p3) {

			Point newvector = VectorMultiplication(point - base_point, rotate_vector);
			double newcos = (newvector * normal)/(newvector.GetModule() * normal.GetModule());
			double currentcos = (current_vector * normal)/(current_vector.GetModule() * normal.GetModule());

			if ( newcos > currentcos ) { // O(1)
				pivot = point;
			}
		}
	}

	return {edge, pivot};
}


Point Edge::PivotAroundEdge(const std::vector<Point> &points) { // O(n^2)
	Point p1 = this->p1;
	Point p2 = this->p2;
	for (const auto& point: points) {
		if ((point != p1 && point != p2)) {
			Edge this_edge = *this;
			Triangle triangle (this_edge, point);
			if (IsFace(triangle, points)) { // O(n)
				return point;
			}
		}
	}
}


bool IsNotUsedEdges(const std::vector<Edge>& edges) {
	bool result = true;
	for (auto edge: edges) {
		result = result && edge.IsProcessed;
	}
	return  !result;
}

template <class T>
bool IsIn(const T& myelement, std::vector<T>& elements) {
	for (int i = 0; i < elements.size(); ++i) {
		if (myelement == elements[i]) {
			elements[i].IsProcessed = true;
			return true;
		}
	}
	return  false;
}


void GiftWrapping(std::vector<Point>& points, std::vector<Triangle> & faces) {
	Triangle t = FindtTriangleOnHull(points); // O(n^2)
	faces.push_back(t);
	std::vector<Edge> edges = t.GetEdges();
	while (IsNotUsedEdges(edges)) { // O(n)
		Edge &newedge = edges.back();
		if (!newedge.IsProcessed) {
			newedge.IsProcessed = true;
			Triangle newtriangle = FindNewTriangle(points, newedge); //O(n) //
			std::vector<Edge> triangles_edges = newtriangle.GetEdges();
			for (const auto& edge: triangles_edges) {
				if (!IsIn(edge, edges)) {
					edges.push_back(edge);
				}
			}
			faces.push_back(newtriangle);
		}

	}
}


void SortByDigit(std::vector<std::vector<int>>& vector, int digit_number) {
	std::sort(vector.begin(), vector.end(),
			  [digit_number](const std::vector<int>& a, const std::vector<int>&b) {
				  return a[digit_number] < b[digit_number];
			  });
}


void Start() {

	int m; // число тестов
	std::cin>>m;

	for (int i = 0; i < m; ++i) {
		int n; // число точек
		std::cin>>n;
		std::vector<Point> points;
		std::vector<Triangle> faces;
		for (int j = 0; j < n; ++j) {
			int x,y,z;
			std::cin>>x>>y>>z;
			points.emplace_back(Point(x,y,z,j));
		}

		GiftWrapping(points, faces);

		std::cout<<faces.size()<<std::endl;

		std::vector<std::vector<int>> lexic_order(faces.size());
		for (int k = 0; k < faces.size(); ++k) {
			lexic_order[k].push_back(3);
			for (auto point: faces[k].GetPointsInProperOrder(points)) {
				lexic_order[k].push_back(point.number);
			}
		}
		// sort
		for (int t = lexic_order[0].size() - 1; t > 0 ; --t) {
			SortByDigit(lexic_order, t);
		}
		// output
		for (const auto& face: lexic_order) {
			for (const auto& number: face) {
				std::cout<<number<<' ';
			}
			std::cout<<'\n';
		}
	}
}


bool predicate(const Point& p1, const Point& p2) {
	return (p1 == p2);
}

int main() {

//	Point p1 (0,0,0,0);
//	Point p2 (10,0,0,1);
//	Point p3 (0,10,0,2);
//	Point p4 (10,10,10,3);
//	Point p5 (5,5,10,4);
//
//	std::vector<Point> points = {p1,p2,p3,p4,p5};
//	std::vector<Triangle> faces;
//	GiftWrapping(points, faces);


	Start();

	return  0;
}

//	std::sort(points.begin(), points.end(), [](const Point& p1, const Point& p2){ return p1.number <= p2.number  ; });
//	auto last = std::unique(points.begin(), points.end());
//	points.erase(last, points.end());
//
//	for (auto point : points) {
//		point.Print();
//	}
//
//	std::cout<<'\n';
//
//	Edge edge(p1,p3,p5);
//	Triangle triangle(edge, p5);
//	std::vector<Point> point_tr = GetPointsOfTriangle(triangle);
//	for (auto point : point_tr) {
//		point.Print();
//	}