fork(2) download
copy 
  1. #include <array>
  2. #include <chrono>
  3. #include <iostream>
  4.  
  5. struct point {
  6. 	int x;
  7. 	int y;
  8. };
  9.  
  10. template<std::size_t N>
  11. bool create_polygon_jit(std::array<point, N>& points, int n, int target_n, int gridsize, int curr_area, int& min_area, std::array<point, N>& soln) 
  12. {
  13. 	if (n >= 3)
  14. 	{
  15. 		int x1 = points[n - 3].x - points[n - 2].x, y1 = points[n - 3].y - points[n - 2].y;
  16. 		int x2 = points[n - 1].x - points[n - 2].x, y2 = points[n - 1].y - points[n - 2].y;
  17. 		if (x1 * y2 - x2 * y1 <= 0) // Angle > 180
  18. 			return false;
  19. 		if (x1 * x2 + y1 * y2 > 0)  // Angle >= 90
  20. 			return false;
  21. 		if (points[1].x == 0 and points[n - 1].x == 0)
  22. 			return true;
  23.  
  24. 		int add_area = points[n - 1].x * points[n - 2].y - points[n - 1].y * points[n - 2].x;
  25. 		if (add_area <= 0)
  26. 			return true;
  27.  
  28. 		curr_area += add_area;
  29. 		if (curr_area >= min_area)
  30. 			return true;
  31.  
  32. 		if (n == target_n)
  33. 		{
  34. 			min_area = curr_area;
  35. 			soln = points;
  36. 			return true;
  37. 		}
  38.  
  39. 		int min_i = std::max(0, points[n - 1].x - 3);
  40. 		int max_i = std::min(gridsize, points[n - 1].x + 4);
  41.  
  42. 		int min_j = std::max(- gridsize / 2, points[n - 1].y - 3);
  43. 		int max_j = std::min(gridsize / 2 + 1, points[n - 1].y + 4);
  44.  
  45. 		if (x2 > 0)
  46. 		{
  47. 			if (y2 > 0)
  48. 			{
  49. 				if (x2 > y2)
  50. 				{
  51. 					for (int j = min_j; j < max_j; j++){
  52. 						for (int i = max_i - 1; i > min_i - 1; i--){
  53. 							points[n].x = i;
  54. 							points[n].y = j;
  55. 							if (!create_polygon_jit(points, n + 1, target_n, gridsize, curr_area, min_area, soln))
  56. 								break;
  57. 						}
  58. 						if (points[n].x == max_i - 1)
  59. 							break;
  60. 					}
  61. 				}
  62. 				else
  63. 				{
  64. 					for (int j = max_j - 1; j > min_j - 1; j--)
  65. 					{
  66. 						for (int i = max_i - 1; i > min_i - 1; i--)
  67. 						{
  68. 							points[n].x = i;
  69. 							points[n].y = j;
  70.  
  71. 							if (!create_polygon_jit(points, n + 1, target_n, gridsize, curr_area, min_area, soln))
  72. 								break;
  73. 						}
  74. 						if (points[n].x == max_i - 1)
  75. 							break;
  76. 					}
  77. 				}
  78. 			}
  79. 			else
  80. 			{
  81. 				if (x2 > -y2)
  82. 				{
  83. 					for (int i = max_i - 1; i > min_i - 1; i--)
  84. 					{
  85. 						for (int j = min_j; j < max_j; j++)
  86. 						{
  87. 							points[n].x = i;
  88. 							points[n].y = j;
  89.  
  90. 							if (!create_polygon_jit(points, n + 1, target_n, gridsize, curr_area, min_area, soln))
  91. 								break;
  92. 						}
  93. 						if (points[n].y == min_j)
  94. 							break;
  95. 					}
  96. 				}
  97. 				else
  98. 				{
  99. 					for (int i = min_i; i < max_i; i++)
  100. 					{
  101. 						for (int j = min_j; j < max_j; j++)
  102. 						{
  103. 							points[n].x = i;
  104. 							points[n].y = j;
  105. 							;
  106. 							if (!create_polygon_jit(points, n + 1, target_n, gridsize, curr_area, min_area, soln))
  107. 								break;
  108. 						}
  109. 						if (points[n].y == min_j)
  110. 							break;
  111. 					}
  112. 				}
  113. 			}
  114. 		}
  115. 		else
  116. 		{
  117. 			if (y2 > 0)
  118. 			{
  119. 				if (-x2 > y2)
  120. 				{
  121. 					for (int i = min_i; i < max_i; i++)
  122. 					{
  123. 						for (int j = max_j - 1; j > min_j - 1; j--)
  124. 						{
  125. 							points[n].x = i;
  126. 							points[n].y = j;
  127.  
  128. 							if (!create_polygon_jit(points, n + 1, target_n, gridsize, curr_area, min_area, soln))
  129. 								break;
  130. 						}
  131. 						if (points[n].y == max_j - 1)
  132. 							break;
  133. 					}
  134. 				}
  135. 				else
  136. 				{
  137. 					for (int i = max_i - 1; i > min_i - 1; i--)
  138. 					{
  139. 						for (int j = max_j - 1; j > min_j - 1; j--)
  140. 						{
  141. 							points[n].x = i;
  142. 							points[n].y = j;
  143.  
  144. 							if (!create_polygon_jit(points, n + 1, target_n, gridsize, curr_area, min_area, soln))
  145. 								break;
  146. 						}
  147. 						if (points[n].y == max_j - 1)
  148. 							break;
  149. 					}
  150. 				}
  151. 			}
  152. 			else
  153. 			{
  154. 				if (-x2 > -y2)
  155. 				{
  156. 					for (int j = max_j - 1; j > min_j - 1; j--)
  157. 					{
  158. 						for (int i = min_i; i < max_i; i++)
  159. 						{
  160. 							points[n].x = i;
  161. 							points[n].y = j;
  162.  
  163. 							if (!create_polygon_jit(points, n + 1, target_n, gridsize, curr_area, min_area, soln))
  164. 								break;
  165. 						}
  166. 						if (points[n].x == min_i)
  167. 							break;
  168. 					}
  169. 				}
  170. 				else
  171. 				{
  172. 					for (int j = min_j; j < max_j; j++)
  173. 					{
  174. 						for (int i = min_i; i < max_i; i++)
  175. 						{
  176. 							points[n].x = i;
  177. 							points[n].y = j;
  178.  
  179. 							if (!create_polygon_jit(points, n + 1, target_n, gridsize, curr_area, min_area, soln))
  180. 								break;
  181. 						}
  182. 						if (points[n].x == min_i)
  183. 							break;
  184. 					}
  185. 				}
  186.  
  187. 			}
  188. 		}
  189. 	}
  190. 	else
  191. 	{
  192. 		int min_i = std::max(0, points[n - 1].x - 3);
  193. 		int max_i = std::min(gridsize, points[n - 1].x + 4);
  194.  
  195. 		int min_j = std::max(-gridsize / 2, points[n - 1].y - 3);
  196. 		int max_j = std::min(gridsize / 2, points[n - 1].y + 4);
  197.  
  198. 		for (int i = min_i; i < max_i; i++)
  199. 		{
  200. 			for (int j = min_j; j < max_j; j++)
  201. 			{
  202. 				points[n].x = i;
  203. 				points[n].y = j;
  204. 				create_polygon_jit(points, n + 1, target_n, gridsize, curr_area, min_area, soln);
  205. 			}
  206. 		}
  207. 	}
  208. 	points[n].x = 0;
  209. 	points[n].y = 0;
  210. 	return true;
  211. }
  212.  
  213. int main() {
  214. 	using namespace std::chrono;
  215. 	auto t1 = steady_clock::now();
  216.  
  217. 	const int n = 16;
  218. 	std::array<point, n> points{};
  219.  
  220. 	int gridSize = 11;
  221. 	int minArea = gridSize * gridSize;
  222.  
  223. 	std::array<point, n> result;
  224.  
  225. 	for (point& p : result){
  226. 		p.x = 0;
  227. 		p.y = 0;
  228. 	}
  229.  
  230. 	create_polygon_jit(points, 1, n, gridSize, 0, minArea, result);
  231.  
  232. 	std::cout << "Result: ";
  233. 	for (point& p : result)
  234. 		std::cout << "("<< p.x << ", " << p.y << ") ";
  235. 	std::cout << "\nArea: " << minArea << "\n";
  236.  
  237. 	auto t2 = steady_clock::now();
  238. 	auto time_span = duration_cast<duration<double>>(t2 - t1);
  239. 	std::cout << "Time:" << time_span.count() << " seconds.\n";
  240. }
Success #stdin #stdout 2.66s 5508KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Result: (0, 0) (0, 1) (1, 3) (2, 4) (4, 5) (5, 5) (7, 4) (8, 3) (9, 1) (9, 0) (8, -2) (7, -3) (5, -4) (4, -4) (2, -3) (1, -2) 
Area: 118
Time:2.65948 seconds.
https://ideone.com/rujb3o
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

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!