fork(3) 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[0].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, 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. 					{
  53. 						for (int i = max_i - 1; i > min_i - 1; i--)
  54. 						{
  55. 							points[n].x = i;
  56. 							points[n].y = j;
  57. 							if (!create_polygon_jit(points, n + 1, target_n, gridsize, curr_area, min_area, soln))
  58. 								break;
  59. 						}
  60. 						if (points[n].x == max_i - 1)
  61. 							break;
  62.  
  63. 					}
  64. 				}
  65. 				else
  66. 				{
  67. 					for (int j = max_j - 1; j > min_j - 1; j--)
  68. 					{
  69. 						for (int i = max_i - 1; i > min_i - 1; i--)
  70. 						{
  71. 							points[n].x = i;
  72. 							points[n].y = j;
  73.  
  74. 							if (!create_polygon_jit(points, n + 1, target_n, gridsize, curr_area, min_area, soln))
  75. 								break;
  76. 						}
  77. 						if (points[n].x == max_i - 1)
  78. 							break;
  79. 					}
  80. 				}
  81. 			}
  82. 			else
  83. 			{
  84. 				if (x2 > -y2)
  85. 				{
  86. 					for (int i = max_i - 1; i > min_i - 1; i--)
  87. 					{
  88. 						for (int j = min_j; j < max_j; j++)
  89. 						{
  90. 							points[n].x = i;
  91. 							points[n].y = j;
  92.  
  93. 							if (!create_polygon_jit(points, n + 1, target_n, gridsize, curr_area, min_area, soln))
  94. 								break;
  95. 						}
  96. 						if (points[n].y == min_j)
  97. 							break;
  98. 					}
  99. 				}
  100. 				else
  101. 				{
  102. 					for (int i = min_i; i < max_i; i++)
  103. 					{
  104. 						for (int j = min_j; j < max_j; j++)
  105. 						{
  106. 							points[n].x = i;
  107. 							points[n].y = j;
  108. 							;
  109. 							if (!create_polygon_jit(points, n + 1, target_n, gridsize, curr_area, min_area, soln))
  110. 								break;
  111. 						}
  112. 						if (points[n].y == min_j)
  113. 							break;
  114. 					}
  115. 				}
  116. 			}
  117. 		}
  118. 		else
  119. 		{
  120. 			if (y2 > 0)
  121. 			{
  122. 				if (-x2 > y2)
  123. 				{
  124. 					for (int i = min_i; i < max_i; i++)
  125. 					{
  126. 						for (int j = max_j - 1; j > min_j - 1; j--)
  127. 						{
  128. 							points[n].x = i;
  129. 							points[n].y = j;
  130.  
  131. 							if (!create_polygon_jit(points, n + 1, target_n, gridsize, curr_area, min_area, soln))
  132. 								break;
  133. 						}
  134. 						if (points[n].y == max_j - 1)
  135. 							break;
  136. 					}
  137. 				}
  138. 				else
  139. 				{
  140. 					for (int i = max_i; i > min_i - 1; i--)
  141. 					{
  142. 						for (int j = max_j - 1; j > min_j - 1; j--)
  143. 						{
  144. 							points[n].x = i;
  145. 							points[n].y = j;
  146.  
  147. 							if (!create_polygon_jit(points, n + 1, target_n, gridsize, curr_area, min_area, soln))
  148. 								break;
  149. 						}
  150. 						if (points[n].y == max_j - 1)
  151. 							break;
  152. 					}
  153. 				}
  154. 			}
  155. 			else
  156. 			{
  157. 				if (-x2 > -y2)
  158. 				{
  159. 					for (int j = max_j - 1; j > min_j - 1; j--)
  160. 					{
  161. 						for (int i = min_i; i < max_i; i++)
  162. 						{
  163. 							points[n].x = i;
  164. 							points[n].y = j;
  165.  
  166. 							if (!create_polygon_jit(points, n + 1, target_n, gridsize, curr_area, min_area, soln))
  167. 								break;
  168. 						}
  169. 						if (points[n].x == min_i)
  170. 							break;
  171. 					}
  172. 				}
  173. 				else
  174. 				{
  175. 					for (int j = min_j; j < max_j; j++)
  176. 					{
  177. 						for (int i = min_i; i < max_i; i++)
  178. 						{
  179. 							points[n].x = i;
  180. 							points[n].y = j;
  181.  
  182. 							if (!create_polygon_jit(points, n + 1, target_n, gridsize, curr_area, min_area, soln))
  183. 								break;
  184. 						}
  185. 						if (points[n].x == min_i)
  186. 							break;
  187. 					}
  188. 				}
  189.  
  190. 			}
  191. 		}
  192. 	}
  193. 	else
  194. 	{
  195. 		int min_i = std::max(0, points[n - 1].x - 3);
  196. 		int max_i = std::min(gridsize, points[n - 1].x + 4);
  197.  
  198. 		int min_j = std::max(-gridsize / 2, points[n - 1].y - 3);
  199. 		int max_j = std::min(gridsize / 2, points[n - 1].y + 4);
  200.  
  201. 		for (int i = min_i; i < max_i; i++)
  202. 		{
  203. 			for (int j = min_j; j < max_j; j++)
  204. 			{
  205. 				points[n].x = i;
  206. 				points[n].y = j;
  207. 				create_polygon_jit(points, n + 1, target_n, gridsize, curr_area, min_area, soln);
  208. 			}
  209. 		}
  210. 	}
  211. 	points[n].x = 0;
  212. 	points[n].y = 0;
  213. 	return true;
  214. }
  215.  
  216. int crossproduct(const point& p0, const point& p1, const point& p2) {
  217. 	const int x1 = p1.x - p0.x, y1 = p1.y - p0.y;
  218. 	const int x2 = p2.x - p0.x, y2 = p2.y - p0.y;
  219. 	return x1 * y2 - y1 * x2;
  220. }
  221.  
  222. template<std::size_t N>
  223. int double_area(std::array<point, N>& points) {
  224. 	int sum = 0;
  225. 	for (int i = 2; i < N; i++)
  226. 		sum += crossproduct(points[0], points[i - 1], points[i]);
  227. 	return abs(sum);
  228. }
  229.  
  230. int main() {
  231. 	using namespace std::chrono;
  232. 	auto t1 = steady_clock::now();
  233.  
  234. 	const int n = 14;
  235. 	std::array<point, n> points{};
  236.  
  237. 	int gridSize = 9;
  238. 	int minArea = gridSize * gridSize;
  239.  
  240. 	std::array<point, n> result;
  241. 	create_polygon_jit(points, 1, n, gridSize, 0, minArea, result);
  242.  
  243. 	std::cout << "Result: ";
  244. 	for (point& p : result)
  245. 		std::cout << p.x << ", " << p.y << "  ";
  246. 	std::cout << "\nArea: " << double_area(result) << "\n";
  247.  
  248. 	auto t2 = steady_clock::now();
  249. 	auto time_span = duration_cast<duration<double>>(t2 - t1);
  250. 	std::cout << "Time:" << time_span.count() << " seconds.\n";
  251. }
Success #stdin #stdout 0.01s 5516KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Result: -1257060448, 5293  -1257909344, 5293  -1257058528, 5293  -1257058816, 5293  -1257058528, 5293  -1258269192, 5293  72703, 0  -1259155192, 5293  -1258269040, 5293  -1260869727, 5293  513093640, 21995  513093937, 21995  1, 0  2, 0  
Area: 970349394
Time:0.00028451 seconds.
https://ideone.com/XHwssi
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!