API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Feb 23rd, 2018
89
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 13.35 KB | None | 0 0
raw download clone embed print report
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <limits.h>
  4.  
  5. int*** games;
  6. int number_of_games = 0;
  7. int* number_of_points;
  8. int** pieces;
  9. int num_pieces , counter = 0;
  10. int** points;
  11. int cmp(int *a, int *b){
  12. int* xi = (int*)a;
  13. int* xj = (int*)b;
  14. if(xi[0] < xj[0])return -1;
  15. if(xi[0] > xj[0]) return 1;
  16. if(xi[1] < xj[1])return -1;
  17. if(xi[1] > xj[1])return 1;
  18. }
  19. int* input(){
  20. int *visited;
  21.  
  22. int out = 0;
  23. int pos = 0;
  24. int contador = 0;
  25. int i,j,aux_x,aux_y;
  26. scanf("%d",&num_pieces);
  27. visited = (int*)malloc(num_pieces*sizeof(int));
  28. for(i=0;i<num_pieces;i++){
  29. visited[i] = 1;
  30. }
  31. pieces = (int**)malloc(num_pieces*sizeof(int*));
  32. for(i = 0; i < num_pieces; i++){
  33. scanf("%d %d",&aux_x,&aux_y);
  34. for(j=0;j<pos;j++){
  35. if((aux_x==pieces[j][0] && aux_y==pieces[j][1]) || (aux_y==pieces[j][0] && aux_x==pieces[j][1])){
  36. visited[j]++;
  37. contador++;
  38. out = 1;
  39. break;
  40. }
  41. }
  42. if(out==0){
  43. pieces[pos] = (int*) malloc(2*sizeof(int));
  44. pieces[pos][0] = aux_x;
  45. pieces[pos][1] = aux_y;
  46. pos++;
  47. }
  48. out=0;
  49. }
  50. num_pieces -= contador;
  51. return visited;
  52. }
  53. int** insere(int** points, int num_points,int index,int x1,int y1,int x2,int y2,int n){
  54. // n = -1 eliminate index
  55. // n == 0 del index, insert x1,y1,
  56. // n == 1 del index, insert x1,y1,x2,y2,
  57. //sort
  58. int** aux = (int**) malloc((num_points+n)*sizeof(int*));
  59. int i, j ,aux1,aux2;
  60. if(n == -1){
  61. for(i = 0; i< num_points+n; i++){
  62. aux[i] = (int*) malloc(2 * sizeof(int));
  63. if( i >= index){
  64. aux[i][0] = points[i+1][0];
  65. aux[i][1] = points[i+1][1];
  66. }
  67. else{
  68. aux[i][0] = points[i][0];
  69. aux[i][1] = points[i][1];
  70. }
  71. }
  72. }
  73. else if(n == 0 || n == 1){
  74. for(i = 0 ; i<num_points + n ; i++){
  75. aux[i] = (int*) malloc(2 * sizeof(int));
  76. if( i == index){
  77. aux[i][0] = x1;
  78. aux[i][1] = y1;
  79. }
  80. else if(i < num_points){
  81. aux[i][0] = points[i][0];
  82. aux[i][1] = points[i][1];
  83. }
  84. }
  85. if(n == 1){
  86. aux[num_points][0] = x2;
  87. aux[num_points][1] = y2;
  88. }
  89. }
  90. for(i = 1;i < num_points + n;i++){
  91. j = i - 1;
  92. aux1 = aux[i][0];
  93. aux2 = aux[i][1];
  94. while(j >= 0 && aux[j][0] > aux1){
  95. aux[j+1][0] = aux[j][0];
  96. aux[j+1][1] = aux[j][1];
  97. j--;
  98. }
  99. aux[j+1][0] = aux1;
  100. aux[j+1][1] = aux2;
  101.  
  102. }
  103. return aux;
  104.  
  105.  
  106. }
  107. void printarray(int** array,int size){
  108. int i;
  109. for(i = 0;i<size;i++){
  110. printf("%d %d\n",array[i][0],array[i][1]);
  111. }
  112. printf("\n");
  113. }
  114.  
  115. int check(int** currently_game,int points){
  116. int i,j;
  117. for(i=0;i<number_of_games;i++){
  118. if(number_of_points[i]!=points)
  119. continue;
  120. for(j=0;j<points;j++){
  121. if(games[i][j][0] != currently_game[j][0] || games[i][j][1] != currently_game[j][1]){
  122. break;
  123. }
  124. if(j==points-1){
  125. return 0;
  126. }
  127. }
  128. if(i == number_of_games - 1){
  129. return 1;
  130. }
  131. }
  132. return 0;
  133.  
  134. }
  135. int ** sort(int** pieces, int size){
  136. int i,j;
  137. int* aux = (int*)malloc(2*sizeof(int));
  138. int** arr = (int**)malloc(size*sizeof(int*));;
  139. for(i=0;i<size;i++){
  140. arr[i] = (int*)malloc(2*sizeof(int));
  141. arr[i][0] = pieces[i][0];
  142. arr[i][1] = pieces[i][1];
  143. }
  144. for(i = 0;i<size;i++){
  145. for(j = i+1;j<size;j++){
  146. if(cmp(arr[i],arr[j]) == 1){
  147. aux[0] = arr[i][0];
  148. aux[1] = arr[i][1];
  149. arr[i][0] = arr[j][0];
  150. arr[i][1] = arr[j][1];
  151. arr[j][0] = aux[0];
  152. arr[j][1] = aux[1];
  153. }
  154. }
  155. }
  156. return arr;
  157.  
  158. }
  159. void algo(int** points, int* visited,int num_points,int** currently_game,int points_game){
  160. int i, j, k, max, limx,limy,m = 0;
  161. int** aux;
  162. //printf(" --- %d\n",currently_game[0][1]);
  163. //for(j = 0;j < number_of_games;j++){
  164. //}
  165. //Condição saida
  166. if(num_points <= 2){
  167. for(i = 0; i < num_pieces; i++){
  168. if(visited[i] != 0){
  169. m = 1;
  170. break;
  171. }
  172. if(m != 1 && i == num_pieces-1){
  173. currently_game = sort(currently_game,points_game);
  174.  
  175.  
  176. if(number_of_games != 0){
  177. if(check(currently_game,points_game) == 1){
  178.  
  179. counter++;
  180. number_of_games++;
  181. // games = (int***)realloc(games, (number_of_games)*sizeof(int**));
  182. // games[number_of_games-1] = (int**)malloc(points_game*sizeof(int*));
  183. for(k=0;k<points_game;k++){
  184. //games[number_of_games-1][k] = (int*)malloc(2*sizeof(int));
  185. games[number_of_games-1][k][0] = currently_game[k][0];
  186. games[number_of_games-1][k][1] = currently_game[k][1];
  187. }
  188. //number_of_points = (int*)realloc(number_of_points,number_of_games*sizeof(int));
  189. number_of_points[number_of_games-1] = points_game;
  190. //printf("JOGO:\n");
  191. //printarray(currently_game,points_game);
  192.  
  193.  
  194. }
  195. }else{
  196.  
  197. for(k=0;k<points_game;k++){
  198. //games[number_of_games][k] = (int*)malloc(2*sizeof(int));
  199. games[number_of_games][k][0] = currently_game[k][0];
  200. games[number_of_games][k][1] = currently_game[k][1];
  201. }
  202. //number_of_points = (int*)malloc(sizeof(int));
  203. number_of_points[0] = points_game;
  204. number_of_games++;
  205. counter++;
  206. }
  207. return;
  208. }
  209. }
  210. }
  211.  
  212.  
  213. for(j = 0;j < num_points; j++){
  214. for(i = 0;i < num_pieces; i++){
  215. if(visited[i] > 0){
  216.  
  217. if(j == 0){
  218. limx = points[j+1][0];
  219. limy = INT_MAX;
  220. }
  221. else if(j == (num_points-1)){
  222. limx = INT_MAX;
  223. limy = points[j-1][1];
  224. }
  225. else{
  226. limx = points[j+1][0];
  227. limy = points[j-1][1];
  228. }
  229. //SQUARE
  230. if(pieces[i][0] == pieces[i][1])
  231. max = 1;
  232.  
  233. else
  234. max = 2;
  235. for(k = 0; k < max; k++){
  236. if((points[j][0] + pieces[i][k]) <= limx && (points[j][1] + pieces[i][abs(k-1)]) <= limy ){
  237.  
  238. //add point same y
  239. if(points[j][0] + pieces[i][k] < limx && points[j][1] + pieces[i][abs(k-1)] == limy){
  240. points_game++;
  241. //currently_game = (int**)realloc(currently_game,points_game*sizeof(int*));
  242. //currently_game[points_game-1] = (int*)malloc(2*sizeof(int));
  243. currently_game[points_game-1][0] = points[j][0]+pieces[i][k];
  244. currently_game[points_game-1][1] = points[j][1];
  245. //falta funcao para ordenar currently_game por x e y quando x e igual
  246. aux = insere(points,num_points,j,points[j][0]+pieces[i][k],points[j][1],0,0,0);
  247. visited[i]--;
  248. algo(aux,visited,num_points,currently_game,points_game);
  249. points_game--;
  250. visited[i]++;
  251. }
  252. //add point two points
  253. else if(points[j][0] + pieces[i][k] < limx && points[j][1] + pieces[i][abs(k-1)] < limy){
  254. points_game+=2;
  255. //currently_game = (int**)realloc(currently_game,points_game*sizeof(int*));
  256. //currently_game[points_game-2] = (int*)malloc(2*sizeof(int));
  257. //currently_game[points_game-1] = (int*)malloc(2*sizeof(int));
  258. currently_game[points_game-2][0] = points[j][0];
  259. currently_game[points_game-2][1] = points[j][1]+pieces[i][abs(k-1)];
  260. currently_game[points_game-1][0] = points[j][0]+pieces[i][k];
  261. currently_game[points_game-1][1] = points[j][1];
  262.  
  263. //falta funcao para ordenar currently_game por x e y quando x e igual
  264. aux = insere(points,num_points,j,points[j][0],points[j][1]+pieces[i][abs(k-1)],points[j][0]+pieces[i][k],points[j][1],1);
  265. num_points++;
  266. visited[i]--;
  267. algo(aux,visited,num_points,currently_game,points_game);
  268. visited[i]++;
  269. num_points--;
  270. points_game-=2;
  271. }
  272. //Perfect
  273. else if(points[j][0] + pieces[i][k] == limx && points[j][1] + pieces[i][abs(k-1)] == limy){
  274. aux = insere(points,num_points,j,0,0,0,0,-1);
  275. visited[i]--;
  276. num_points--;
  277. algo(aux,visited,num_points,currently_game,points_game);
  278. num_points++;
  279. visited[i]++;
  280. }
  281. //add point same x
  282. else if(points[j][0] + pieces[i][k] == limx && points[j][1] + pieces[i][abs(k-1)] < limy){
  283. points_game++;
  284. //currently_game = (int**)realloc(currently_game,points_game*sizeof(int*));
  285. //currently_game[points_game-1] = (int*)malloc(2*sizeof(int));
  286. currently_game[points_game-1][0] = points[j][0];
  287. currently_game[points_game-1][1] = points[j][1]+pieces[i][abs(k-1)];
  288. aux = insere(points,num_points,j,points[j][0],points[j][1]+pieces[i][abs(k-1)],0,0,0);
  289. visited[i]--;
  290. algo(aux,visited,num_points,currently_game,points_game);
  291. visited[i]++;
  292. points_game--;
  293. }
  294.  
  295. }
  296.  
  297.  
  298. }
  299. }
  300. }
  301. }
  302. }
  303.  
  304. int main()
  305. {
  306. int i, j, max;
  307. int** points;
  308. int* used_pieces = input();
  309. points = (int**)malloc(20*sizeof(int*));
  310. games = (int***)malloc(20*sizeof(int**));
  311. number_of_points = (int*)malloc(20*sizeof(int));
  312. int** currently_game = (int**)malloc(20*sizeof(int*));
  313. for(i=0;i<8;i++){
  314. games[i] = (int**)malloc(20*sizeof(int*));
  315. for(j = 0;j<8;j++){
  316. games[i][j] = (int*)malloc(2*sizeof(int));
  317. }
  318. }
  319. for(i = 0; i < 8 ; i++){
  320. points[i] = (int*)malloc(20*sizeof(int));
  321. currently_game[i] = (int*)malloc(2*sizeof(int));
  322. }
  323.  
  324. for(i=0;i<num_pieces;i++){
  325. points[0][0] = pieces[i][0];
  326. points[0][1] = 0;
  327. points[1][0] = 0;
  328. points[1][1] = pieces[i][1];
  329. //SQUARE
  330. points = insere(points,3,2,0,0,0,0,-1);
  331. if(pieces[0][0] == pieces[0][1]){
  332. max = 1;
  333. }
  334. else
  335. max = 2;
  336. for(j = 0;j < max; j++ ){
  337. if(j == 1){
  338. points[0][0] = pieces[i][1];
  339. points[0][1] = 0;
  340. points[1][0] = 0;
  341. points[1][1] = pieces[i][0];
  342. points = insere(points,3,2,0,0,0,0,-1);
  343. }
  344.  
  345. //currently_game[0] = (int*)malloc(2*sizeof(int));
  346. //currently_game[1] = (int*)malloc(2*sizeof(int));
  347. currently_game[0][0] = points[0][0];
  348. currently_game[0][1] = points[0][1];
  349. currently_game[1][0] = points[1][0];
  350. currently_game[1][1] = points[1][1];
  351. used_pieces[i]--;
  352. algo(points,used_pieces,2,currently_game,2);
  353. used_pieces[i]++;
  354. }
  355. }
  356. for(i = 0;i<number_of_games;i++){
  357. printf("JOGO:\n");
  358. printarray(games[i],number_of_points[i]);
  359. }
  360. printf("%d",counter);
  361. return 0;
  362. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!