fork download 
  1. #include <set>
  2. #include <array>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <iostream>
  6. #include <cfloat>
  7.  
  8. typedef std::array<double, 3> Point3D;
  9.  
  10. double squareDistancePoints(const Point3D& a, const Point3D& b)
  11. {
  12. 	double squareSum = 0;
  13.  
  14. 	for (size_t i = 0; i < a.size(); ++i)
  15. 		squareSum += pow(a[i] - b[i], 2);
  16.  
  17. 	return squareSum;
  18. }
  19.  
  20. int main(int argc, char **argv)
  21. {
  22. 	std::vector<Point3D> orderedMatrix;
  23.  
  24. 	// Sortierte Punkte eines Rechtecks
  25. 	orderedMatrix.push_back({ 0, 0, 0 });
  26. 	orderedMatrix.push_back({ 50, 0, 0 });
  27. 	orderedMatrix.push_back({ 100, 0, 0 });
  28. 	orderedMatrix.push_back({ 100, 50, 0 });
  29. 	orderedMatrix.push_back({ 100, 100, 0 });
  30. 	orderedMatrix.push_back({ 50, 100, 0 });
  31. 	orderedMatrix.push_back({ 0, 100, 0 });
  32. 	orderedMatrix.push_back({ 0, 50, 0 });
  33.  
  34. 	// Unsortierte Punkte erzeugen (einfach zufällig durcheinandergeworfen)
  35. 	std::vector<Point3D> matrix = orderedMatrix;
  36. 	for (size_t i = 0; i < matrix.size(); ++i)
  37. 		std::swap(matrix[i], matrix[rand() % matrix.size()]);
  38.  
  39. 	// Duplikate entfernen 
  40. 	// (würde das nach der Sortierung nicht besser passen? 
  41. 	//  Außerdem ein bitweiser Vergleich von double-Werten?)
  42. 	std::set<Point3D> set(matrix.begin(), matrix.end());
  43. 	matrix.erase(
  44. 		std::remove_if(matrix.begin(), matrix.end(), 
  45. 			[&set](const Point3D& item) {return !set.erase(item); }), 
  46. 		matrix.end());
  47.  
  48. 	// Vorher
  49. 	std::cout << "Before: " << std::endl;
  50. 	for (const auto& p : matrix)
  51. 		std::cout << p[0] << " / " << p[1] << " / " << p[2] << std::endl;
  52.  
  53. 	// Sortieren
  54. 	for (auto it = matrix.begin(); it != matrix.end(); ++it)
  55. 	{
  56. 		std::cout << "START " 
  57. 			<< it->at(0) << " / " 
  58. 			<< it->at(1) << " / " 
  59. 			<< it->at(2) << std::endl;
  60.  
  61. 		auto bestIt = matrix.end();
  62.  
  63. 		double bestSquareDistance = DBL_MAX;
  64.  
  65. 		for (auto nextIt = it + 1; nextIt != matrix.end(); ++nextIt)
  66. 		{
  67. 			const auto squareDistance = squareDistancePoints(*it, *nextIt);
  68. 			std::cout << "   TRY " 
  69. 				<< nextIt->at(0) << " / " 
  70. 				<< nextIt->at(1) << " / " 
  71. 				<< nextIt->at(2) << " d=" << sqrt(squareDistance) << std::endl;
  72.  
  73. 			if (squareDistance < bestSquareDistance)
  74. 			{
  75. 				bestSquareDistance = squareDistance;
  76. 				bestIt = nextIt;
  77. 			}
  78. 		}
  79. 		if (bestIt != matrix.end())
  80. 		{
  81. 			std::cout << "   BEST " 
  82. 				<< bestIt->at(0) << " / " 
  83. 				<< bestIt->at(1) << " / " 
  84. 				<< bestIt->at(2) << " d=" << sqrt(bestSquareDistance) << std::endl;
  85.  
  86. 			std::swap(*(it + 1), *bestIt);
  87. 		}
  88.  
  89. 	}
  90.  
  91. 	// Nachher
  92. 	std::cout << "After: " << std::endl;
  93. 	for (const auto& p : matrix)
  94. 		std::cout << p[0] << " / " << p[1] << " / " << p[2] << std::endl;
  95.  
  96. 	return 0;
  97. }
Success #stdin #stdout 0s 3468KB
comments (?)
stdin 
Standard input is empty
stdout 
Before: 
0 / 50 / 0
100 / 100 / 0
50 / 0 / 0
100 / 50 / 0
50 / 100 / 0
0 / 0 / 0
0 / 100 / 0
100 / 0 / 0
START 0 / 50 / 0
   TRY 100 / 100 / 0 d=111.803
   TRY 50 / 0 / 0 d=70.7107
   TRY 100 / 50 / 0 d=100
   TRY 50 / 100 / 0 d=70.7107
   TRY 0 / 0 / 0 d=50
   TRY 0 / 100 / 0 d=50
   TRY 100 / 0 / 0 d=111.803
   BEST 0 / 0 / 0 d=50
START 0 / 0 / 0
   TRY 50 / 0 / 0 d=50
   TRY 100 / 50 / 0 d=111.803
   TRY 50 / 100 / 0 d=111.803
   TRY 100 / 100 / 0 d=141.421
   TRY 0 / 100 / 0 d=100
   TRY 100 / 0 / 0 d=100
   BEST 50 / 0 / 0 d=50
START 50 / 0 / 0
   TRY 100 / 50 / 0 d=70.7107
   TRY 50 / 100 / 0 d=100
   TRY 100 / 100 / 0 d=111.803
   TRY 0 / 100 / 0 d=111.803
   TRY 100 / 0 / 0 d=50
   BEST 100 / 0 / 0 d=50
START 100 / 0 / 0
   TRY 50 / 100 / 0 d=111.803
   TRY 100 / 100 / 0 d=100
   TRY 0 / 100 / 0 d=141.421
   TRY 100 / 50 / 0 d=50
   BEST 100 / 50 / 0 d=50
START 100 / 50 / 0
   TRY 100 / 100 / 0 d=50
   TRY 0 / 100 / 0 d=111.803
   TRY 50 / 100 / 0 d=70.7107
   BEST 100 / 100 / 0 d=50
START 100 / 100 / 0
   TRY 0 / 100 / 0 d=100
   TRY 50 / 100 / 0 d=50
   BEST 50 / 100 / 0 d=50
START 50 / 100 / 0
   TRY 0 / 100 / 0 d=50
   BEST 0 / 100 / 0 d=50
START 0 / 100 / 0
After: 
0 / 50 / 0
0 / 0 / 0
50 / 0 / 0
100 / 0 / 0
100 / 50 / 0
100 / 100 / 0
50 / 100 / 0
0 / 100 / 0
https://ideone.com/OeCpdG
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!