Advertisement
faunuss

Untitled

Nov 25th, 2017
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 10.89 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4. #include <stack>
  5. #include <set>
  6. #include <algorithm>
  7. using namespace std;
  8.  
  9.  
  10.  
  11. class ConvexHull {
  12. public:
  13. ConvexHull(size_t num) {
  14. dots.clear();
  15. num_dots = num;
  16. }
  17.  
  18. void read_dots() {
  19. // Считываем все точки
  20. for(int i = 0; i < num_dots; i++) {
  21. double x = 0;
  22. double y = 0;
  23. double z = 0;
  24. cin >> x >> y >> z;
  25. Point tmp(x,y,z,i);
  26. dots.push_back(tmp);
  27. }
  28. }
  29.  
  30. void print_convex() {
  31. vector<Triangle> ans;
  32. Triangle first_triangle = Initialize();
  33. stack<Triangle> edges;
  34. edges.push(first_triangle);
  35.  
  36. vector<vector<bool>> edges_proceed;
  37.  
  38. edges_proceed.resize(num_dots);
  39. for(int i = 0; i < num_dots; i++){
  40. edges_proceed[i].resize(num_dots);
  41. }
  42.  
  43.  
  44. while(!edges.empty()) {
  45. Triangle tmp_trinagle = edges.top(); edges.pop();
  46. Edge e = tmp_trinagle.edge;
  47. Point p1 = e.first;
  48. Point p2 = e.second;
  49.  
  50. if(!edges_proceed[p1.num][p2.num]) {
  51. Point p3 = find_dot(tmp_trinagle);
  52. set<int> s_tmp = {p1.num, p2.num, p3.num};
  53.  
  54. Triangle new_Triange(p1,p2,p3);
  55.  
  56. Edge tmp_edge(p2,p3);
  57. new_Triange.edge = tmp_edge;
  58. new_Triange.first = p2; new_Triange.second = p3;
  59. edges.push(new_Triange);
  60.  
  61. tmp_edge.first = p3; tmp_edge.second = p1;
  62. new_Triange.edge = tmp_edge;
  63. new_Triange.first = p3; new_Triange.second = p1;
  64. edges.push(new_Triange);
  65.  
  66. edges_proceed[p1.num][p2.num] = true;
  67. edges_proceed[p2.num][p1.num] = true;
  68.  
  69. if (new_Triange.first.num != 0 && new_Triange.second.num != 0 && new_Triange.third.num != 0) {
  70. new_Triange.sort_dots(dots[0]);
  71. }
  72. else if (new_Triange.first.num != 1 && new_Triange.second.num != 1 && new_Triange.third.num != 1) {
  73. new_Triange.sort_dots(dots[1]);
  74. }
  75. else if (new_Triange.first.num != 2 && new_Triange.second.num != 2 && new_Triange.third.num != 2) {
  76. new_Triange.sort_dots(dots[2]);
  77. }
  78. else {
  79. new_Triange.sort_dots(dots[3]);
  80. }
  81.  
  82. ans.push_back(new_Triange);
  83. }
  84. }
  85.  
  86.  
  87. std::sort(ans.begin(), ans.end(), compare_triangle);
  88.  
  89. cout << ans.size() << "\n"; // Вывод данных
  90. for(auto i:ans) {
  91. cout << "3 " << i.first.num << " " << i.second.num << " " << i.third.num << "\n";
  92. }
  93. }
  94. private:
  95. const double MAX_COORDINATE = 1000000;
  96.  
  97. // Структура, описывающая точку
  98. struct Point{
  99. double x; // Координата точки по x
  100. double y; // Координата точки по y
  101. double z; // Координата точки по z
  102. int num; // Номер точки
  103.  
  104. Point(double X, double Y, double Z, int Number) : x(X), y(Y), z(Z), num(Number) {}
  105. };
  106.  
  107. // Векторное умножение
  108. Point static CrossProduct (const Point& A,const Point& B) {
  109. return Point{.x = A.z*B.y-A.y*B.z,
  110. .y = A.x*B.z-A.z*B.x,
  111. .z = A.y*B.x-A.x*B.y,
  112. .num = -1};
  113. }
  114.  
  115. // Скалярное умножение
  116. double static Scalar(const Point& A,const Point& B) {
  117. return(A.x*B.x+A.y*B.y+A.z*B.z);
  118. }
  119.  
  120. // Структура, описывающая плоскость
  121. struct Flat { // Ax + By + Cz + D = 0
  122. double A;
  123. double B;
  124. double C;
  125. double D;
  126.  
  127. // Конструктор плоскости от значений чисел
  128. Flat(double a, double b, double c, double d) : A(a), B(b), C(c), D(d) {}
  129.  
  130. // Констуктор плоскости от значений точек
  131. Flat(Point p, Point p0, Point tmp) {
  132. double a2 = p0.x - p.x; double b2 = p0.y - p.y; double c2 = p0.z - p.z;
  133. double a3 = tmp.x - p.x; double b3 = tmp.y - p.y; double c3 = tmp.z - p.z;
  134.  
  135. A = b2*c3-c2*b3;
  136. B = c2*a3-a2*c3;
  137. C = a2*b3-b2*a3;
  138. D = -1*p.x*A -p.y*B - p.z*C;
  139. }
  140. };
  141.  
  142. // Угол между плоскостями
  143. double get_angle(const Flat& First,const Flat& Second) {
  144. double numerator = abs(First.A*Second.A + First.B*Second.B + First.C*Second.C);
  145. double denominator = sqrt(First.A*First.A + First.B*First.B + First.C*First.C);
  146. denominator *= sqrt(Second.A*Second.A + Second.B*Second.B + Second.C*Second.C);
  147. return acos(numerator/denominator);
  148. }
  149.  
  150. // Ребро задается двумя точками
  151. struct Edge {
  152. Point first; // Первая точка
  153. Point second; // Вторая
  154.  
  155. Edge(Point F,Point S): first(F), second(S) {}
  156. };
  157.  
  158. // Треугольник задается тремя точками
  159. struct Triangle {
  160. Point first; // Первая точка
  161. Point second; // Вторая точка
  162. Point third; // Третья точка
  163. Edge edge; // Опорное ребро
  164.  
  165.  
  166. void sort_dots(const Point& help){
  167. if(first.num < second.num && first.num < third.num) {
  168. Point u1(second.x - first.x,second.y - first.y,second.z - first.z,-1);
  169. Point u2(third.x - first.x,third.y - first.y,third.z - first.z,-1);
  170. Point u3(help.x - first.x,help.y - first.y,help.z - first.z,-1);
  171.  
  172. if(Scalar(CrossProduct(u1,u2),u3) < 0) {
  173. Point T = second; second = third; third = T;
  174. }
  175. }
  176. else if(second.num < first.num && second.num < third.num) {
  177. Point T = second; second = first; first = T;
  178.  
  179. Point u1(second.x - first.x,second.y - first.y,second.z - first.z,-1);
  180. Point u2(third.x - first.x,third.y - first.y,third.z - first.z,-1);
  181. Point u3(help.x - first.x,help.y - first.y,help.z - first.z,-1);
  182.  
  183. if(Scalar(CrossProduct(u1,u2),u3) < 0) {
  184. T = second; second = third; third = T;
  185. }
  186. }
  187. else {
  188. Point T = third; third = first; first = T;
  189. Point u1(second.x - first.x,second.y - first.y,second.z - first.z,-1);
  190. Point u2(third.x - first.x,third.y - first.y,third.z - first.z,-1);
  191. Point u3(help.x - first.x,help.y - first.y,help.z- first.z,-1);
  192.  
  193. if(Scalar(CrossProduct(u1,u2),u3) < 0) {
  194. T = second; second = third; third = T;
  195. }
  196. }
  197. }
  198.  
  199. Triangle(Point F,Point S,Point T) : first(F), second(S), third(T), edge(F, S) {}
  200. };
  201.  
  202. // Для сортировки треугольников
  203. static bool compare_triangle(const Triangle& First,const Triangle& Second) {
  204. if(First.first.num < Second.first.num) {
  205. return true;
  206. }
  207. if(First.first.num > Second.first.num) {
  208. return false;
  209. }
  210. if(First.second.num < Second.second.num) {
  211. return true;
  212. }
  213. if(First.second.num > Second.second.num) {
  214. return false;
  215. }
  216. if(First.third.num <= Second.third.num) {
  217. return true;
  218. }
  219. return false;
  220. }
  221.  
  222. // Инициализация первых двух точек - первого ребра
  223. Triangle Initialize() {
  224. Point first_point(MAX_COORDINATE, MAX_COORDINATE, MAX_COORDINATE, -1); // Первая точка инициализации
  225.  
  226. for (int i = 0; i < num_dots; i++) { // Находим эту самую точку first_point
  227. if (dots[i].z < first_point.z) {
  228. first_point = dots[i];
  229. } else if (dots[i].z == first_point.z) {
  230. if (dots[i].x < first_point.x) {
  231. first_point = dots[i];
  232. } else if (dots[i].x == first_point.x) {
  233. if (dots[i].y < first_point.y) {
  234. first_point = dots[i];
  235. }
  236. }
  237. }
  238. }
  239.  
  240. Flat H(0, 0, 1, -1 * first_point.z); // z - first_point.z = 0 - уравнение плоскости перпендекулярной Oz и проходящий через first_point
  241.  
  242. // В качестве l возьмем прямую проходящую через first_point и какую-то случайную точку
  243. Point l_point(rand() % 100 + 1985, rand() % 30 + 1985, first_point.z, -1);
  244.  
  245. Point second_point(MAX_COORDINATE, MAX_COORDINATE, MAX_COORDINATE, -1); // Вторая точка первого треугольника
  246. double max_angle = M_PI;
  247.  
  248. for (int i = 0; i < num_dots; i++) { // Находим точку second_point, через которую пройдет H
  249. if (i != first_point.num) {
  250. Point tmp = dots[i];
  251. Flat tmp_G(first_point, l_point, tmp);
  252. double angle = get_angle(H, tmp_G);
  253. if (angle < max_angle) {
  254. max_angle = angle;
  255. second_point = tmp;
  256. }
  257. }
  258. }
  259. Triangle to_return(first_point,second_point,l_point);
  260. return to_return;
  261. }
  262.  
  263. Point find_dot(Triangle T) {
  264. Point first_point = T.first;
  265. Point second_point = T.second;
  266.  
  267. Flat G(first_point,second_point,T.third);
  268. double max_angle = M_PI;
  269.  
  270. Point the_new_point(MAX_COORDINATE, MAX_COORDINATE, MAX_COORDINATE, -1);
  271. for(int i = 0; i < num_dots; i++) {
  272. if(i != first_point.num && i != second_point.num ){
  273. Point tmp_point = dots[i];
  274. Flat tmp_flat(first_point, second_point, tmp_point);
  275. double angle = get_angle(G, tmp_flat);
  276. if(angle < max_angle){
  277. the_new_point = tmp_point;
  278. max_angle = angle;
  279. }
  280. }
  281. }
  282. return the_new_point;
  283. }
  284.  
  285.  
  286. vector<Point> dots;
  287. size_t num_dots;
  288. };
  289.  
  290. int main() {
  291. int num_tests = 0; // Количество тестов
  292. cin >> num_tests;
  293.  
  294. for(int test = 0; test < num_tests; test++) {
  295. size_t num_dots = 0; // Количество точек в тесте
  296. cin >> num_dots;
  297.  
  298. ConvexHull algo(num_dots);
  299. algo.read_dots();
  300. algo.print_convex();
  301. }
  302. return 0;
  303. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement