rendered paste body#include <stdio.h>#include <stdlib.h>#include <string.h>#include <math.h>#define PN 52 struct path{ double length; unsigned short int pcount; unsigned short int p_used[PN]; unsigned short int points[PN];}; const unsigned short int a_used[PN] ={ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,}; double pa[PN][2] = { {525, 187}, {295, 946}, {364, 787}, {533, 5}, {203, 862}, {625, 11}, {824, 675}, {369, 58}, {308, 785}, {726, 766}, {155, 22}, {197, 879}, {881, 599}, {862, 953}, {328, 391}, {983, 744}, {426, 695}, {478, 583}, {821, 911}, { 79, 60}, {665, 272}, {191, 773}, {114, 281}, {800, 567}, {222, 693}, {846, 961}, {215, 740}, {353, 769}, {750, 726}, {908, 909}, {309, 658}, {867, 649}, {592, 106}, { 16, 637}, { 54, 796}, {449, 649}, {980, 654}, {594, 819}, {764, 101}, {921, 307}, {928, 647}, {738, 196}, {550, 578}, {478, 489}, {449, 755}, {189, 415}, {433, 545}, {967, 478}, {149, 416}, {144, 117}, {298, 972}, {854, 144},}; double pd[PN][PN]; double oa[8][2] = { {+1000, +1000}, {+1000, -1000}, {+1000, + 0}, {-1000, -1000}, {-1000, +1000}, {-1000, + 0}, {+ 0, +1000}, {+ 0, -1000},}; double dist(double (*p0)[2], double (*p1)[2]){ double dist = 0; double temp = 0; int i = 0; dist = sqrt(pow(((*p0)[0] - (*p1)[0]), 2) + pow(((*p0)[1] - (*p1)[1]), 2)); for (i = 0; i < 8; i++) { temp = sqrt(pow(((*p0)[0] - (*p1)[0] + oa[i][0]), 2) + pow(((*p0)[1] - (*p1)[1] + oa[i][1]), 2)); if (temp < dist) { dist = temp; } } return(dist);} void fill(){ int x = 0; int y = 0; for (x = 0; x < PN; x++) { for (y = 0; y < PN; y++) { pd[x][y] = dist(&pa[x], &pa[y]); } }} void padd(struct path *p_temp, unsigned short int pnum){ p_temp->points[p_temp->pcount] = pnum; p_temp->p_used[pnum] = 1; p_temp->length += pd[p_temp->points[p_temp->pcount-1]][p_temp->points[p_temp->pcount]]; p_temp->pcount++;} void pdel(struct path *p_temp){ p_temp->pcount--; p_temp->length -= pd[p_temp->points[p_temp->pcount-1]][p_temp->points[p_temp->pcount]]; p_temp->p_used[p_temp->points[p_temp->pcount]] = 0; p_temp->points[p_temp->pcount] = 0;} unsigned short int pmax(struct path *p_temp){ unsigned short int temp = 0; unsigned short int pmax = 0; for (temp = 0; temp < PN; temp++) { if (p_temp->p_used[temp] == 0) { pmax = temp; } } return(pmax);} unsigned short int pnxt(struct path *p_temp, unsigned short int pprv){ unsigned short int temp = 0; unsigned short int pnxt = 0; for (temp = pprv; temp < PN && pnxt == 0; temp++) { if (p_temp->p_used[temp] == 0) { pnxt = temp; } } return(pnxt);} void dump(struct path *p_temp){ unsigned short int temp = 0; while (temp < PN) { printf("%02d ", p_temp->points[temp]); temp++; } printf(" : %7.18g\n", p_temp->length);} int main(){ unsigned short int pnum = 1; struct path p_best; struct path p_temp; memset(&p_best, 0, sizeof(struct path)); memset(&p_temp, 0, sizeof(struct path)); fill(); p_best.length = 32768; p_temp.pcount = 1; p_temp.p_used[0] = 1; while (pnum < PN) { if (p_temp.p_used[pnum] == 0) { padd(&p_temp, pnum); if (0 & (p_temp.length >= p_best.length)) { pdel(&p_temp); } else { pnum = 0; } } if (memcmp(&p_temp.p_used, &a_used, sizeof(a_used)) == 0) { p_temp.length += pd[p_temp.points[0]][p_temp.points[p_temp.pcount-1]]; dump(&p_temp); if (p_temp.length < p_best.length) { memcpy (&p_best, &p_temp, sizeof(struct path)); } p_temp.length -= pd[p_temp.points[0]][p_temp.points[p_temp.pcount-1]]; do { pnum = p_temp.points[p_temp.pcount-1]; pdel(&p_temp); } while (pnum >= pmax(&p_temp)); pnum = pnxt(&p_temp, pnum); } pnum++; } printf(" \n"); printf("%02d\n", pnum); printf(" \n"); dump(&p_best); return 0;}