fork download
copy 
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<time.h>
  5. #include<algorithm>
  6.  
  7. #define INF 200000000
  8.  
  9. using namespace std;
  10.  
  11. struct Point
  12. {
  13. 	int x[3];
  14. 	Point(){};
  15. };
  16.  
  17. inline bool operator<(const Point &a, const Point &b)
  18. {
  19. 	if(a.x[0] != b.x[0])
  20. 		return a.x[0] < b.x[0];
  21. 	if(a.x[1] != b.x[1])
  22. 		return a.x[1] < b.x[1];
  23. 	return a.x[2] < b.x[2];
  24. }
  25.  
  26. Point point[10];
  27.  
  28. inline void swap(int &a, int &b)
  29. {
  30. 	int c=a;
  31. 	a=b;
  32. 	b=c;
  33. }
  34.  
  35. bool ok(Point v[])
  36. {
  37. //	int dist[];
  38. //	int dist_count[];
  39. 	Point ans[9];
  40. 	for(int i = 1 ; i <= 8 ; i++)
  41. 		ans[i] = v[i];
  42. 	sort(ans+1, ans+9);
  43. 	int num[3];
  44. 	for(int i = 0 ; i < 3 ; i++)
  45. 	{
  46. 		num[i] = ans[2].x[i] - ans[1].x[i];
  47. 		for(int j = 3 ; j < 8 ; j+=2)
  48. 		{
  49. 			if(ans[j+1].x[i] - ans[j].x[i]  !=  num[i])
  50. 				return false;
  51. 		}
  52. 	}
  53. 	if(num[0]==0 && num[1]==0 && num[2]==0)
  54. 		return false;
  55. 	return true;
  56. }
  57.  
  58. inline long long count_e()
  59. {
  60. 	long long E = 0;
  61. 	for(int i = 1 ; i < 8 ; i++)
  62. 	{
  63. 		for(int j = i+1 ; j <= 8 ; j++)
  64. 		{
  65. 			long long a,b,c;
  66. 			a = (point[j].x[0] - point[i].x[0]);
  67. 			b = (point[j].x[1] - point[i].x[1]);
  68. 			c = (point[j].x[2] - point[i].x[2]);
  69. 	//		printf("%d,%d,%d\n", a, b, c);
  70. 			if(a==0 && b==0 && c==0)
  71. 				return 123456789;
  72. 			E += (a*a)+(b*b)+(c*c);
  73. 		}
  74. 	}
  75. //	puts("");
  76. 	return E;
  77. }
  78.  
  79. int main()
  80. {
  81. 	srand(clock());
  82.  
  83.  
  84. 	Point low_state[9];
  85. 	for(int i = 1 ; i <= 8 ; i++)
  86. 		scanf("%d%d%d", &point[i].x[0], &point[i].x[1], &point[i].x[2]);
  87.  
  88. 	long long low = INF;
  89.  
  90.  
  91. 	for(int i = 0 ; i < 50000 ; i++)
  92. 	{
  93. 		long long E = count_e();
  94. 		if(E <= low && ok(point))
  95. 		{
  96. 			for(int i = 1 ; i <= 8 ; i++)
  97. 				low_state[i] = point[i];
  98. 			low = E;
  99. 		}
  100. 		for(int j = 0 ; j < 100 ; j++)
  101. 		{
  102. 			int line = rand()%7+1;
  103. 			int sa = rand()%3;
  104. 			int sb = (sa+1)%3;
  105. 			swap(point[line].x[sa], point[line].x[sb]);
  106. 		}
  107. 	}
  108.  
  109.  
  110. //	cout << "LOW = " << low << endl;
  111. 	if(low != 123456789 && ok(low_state))
  112. 	{
  113. 		puts("YES");
  114. 		for(int i = 1 ; i <= 8 ; i++)
  115. 		{
  116. 			printf("%d %d %d\n", low_state[i].x[0], low_state[i].x[1], low_state[i].x[2]);
  117. 		}
  118. 	}
  119. 	else
  120. 		puts("NO");
  121.  
  122. 	return 0;
  123. }
  124.  
Success #stdin #stdout 0.3s 3352KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/7DEyXZ
language:
C++ (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!