/* * Fences Make Good Neighbors solution * ICPC East Division * Fred Pickel, Greater NY Region - 08/01/2024 */ #include #include #include #include #include typedef unsigned char BYTE; #define MAX_VERTS 80 #define MIN_SON_DIST (0.5) #define BIG (1.0E30) #define BETWEEN 0x10 #define THRU_SON 0x20 #define NO_USE 0x30 #define LINE_THRU_PT (-23) //#define FAIL_SON_DIST double vx[MAX_VERTS+1], vy[MAX_VERTS+1]; double px1, py1, px2, py2, pvx, pvy; double perimeter; int nverts; double len[2*MAX_VERTS][2*MAX_VERTS]; // lenghts of edges and diaglonals i < j so j,I+nverts double cost[MAX_VERTS][2*MAX_VERTS]; // cost of triangulation of polgon i ...j resp j ... i+nverts (-1) if not set BYTE InMasks[MAX_VERTS][MAX_VERTS]; // iline form v[i] to v[j] left or rt of P1 P2 int InOther[MAX_VERTS]; // if >0 val at i gives other end of line between P1 and P2 int InCount[MAX_VERTS]; // number of lines from V[i] passing between P1 and P2 // find verts top bot where // top = least j with i->j between p1 and p2 and // bot = max j with i->j between p1 and p2 // if not such verts return -1; int FindTopBottom(int i, int *ptop, int *pbot) { int top, bot, nbot, ntop, count; top = bot = InOther[i]; if((InMasks[i][top] & BETWEEN) == 0) { return -21; } count = 1; ntop = (top - 1 + nverts) % nverts; while(InMasks[i][ntop] & BETWEEN) { top = ntop; ntop = (top - 1 + nverts) % nverts; count++; } nbot = (bot + 1) %nverts; while(InMasks[i][nbot] & BETWEEN) { bot = nbot; nbot = (bot + 1) %nverts; count++; } if(count < 2) return (-22); *ptop = top; *pbot = bot; return 0; } double FindCost(int i, int j) { int k; double cur , ret, base; if((j <= i) || (j >= (i+nverts))) { fprintf(stderr, "FindCost: j (%d) not in range i(%d) < j < i + nverts(%d)\n", j, i, i + nverts); return -1.0; } if((i >= nverts) && (j >= nverts)) { i -= nverts; j -= nverts; } base = len[i][j]; if(j == (i+1)) return 0.0; if(cost[i][j] > 0.0) return cost[i][j]; ret = BIG; for(k = i+1; k < j ; k++) { if((InMasks[i %nverts][k%nverts] & NO_USE) || (InMasks[k %nverts][j%nverts] & NO_USE)) { continue; } cur = base + len[i][k] + len[k][j] + FindCost(i,k) + FindCost(k,j); if(cur < ret) ret = cur; } cost[i][j] = ret; return ret; } double FindMinCost() { int i, top, bot, j, k, m; double cur, ret; ret = BIG; for(i = 0; i < nverts-1 ; i++) { if(InCount[i] < 2) { continue; } if(FindTopBottom(i, &top, &bot) != 0) { continue; } cur = len[i][top] + len[i][bot] + len[top][bot]; j = top; if( j < i) j += nverts; k = i; if(k < bot) k += nverts; m = bot; if(m < top) m += nverts; cur += FindCost(i, j); cur += FindCost(bot, k); cur += FindCost(top, m); if(cur < ret) ret = cur; } return ret; } int CompInInfo(int i, int j, double vx, double vy, double dvx, double dvy, double len) { double dp1x, dp1y, dp2x, dp2y, dir1, dir2; dp1x = px1 - vx; dp1y = py1 - vy; dp2x = px2 - vx; dp2y = py2 - vy; dir1 = (dp1x*dvy - dp1y*dvx)/len; dir2 = (dp2x*dvy - dp2y*dvx)/len; if((fabs(dir1) < MIN_SON_DIST) || (fabs(dir2) < MIN_SON_DIST)) { #ifdef FAIL_SON_DIST return LINE_THRU_PT; #else InMasks[i][j] = THRU_SON; InMasks[j][i] = THRU_SON; #endif } else if((dir1*dir2) < 0.0) { InOther[i] = j; InOther[j] = i; InCount[i]++; InCount[j]++; InMasks[i][j] = BETWEEN; InMasks[j][i] = BETWEEN; } return 0; } int ProcessPoints() { int i, j, ret; double test; double dvx, dvy, pdvx, pdvy; for(i = 0; i < nverts ; i++) { for(j = 0 ; j < 2*nverts ; j++) { cost[i][j] = -1.0; } } for(i = 0; i < nverts ; i++) { InOther[i] = -1; InCount[i] = 0; for(j = 0 ; j < nverts ; j++) { InMasks[i][j] = 0; } } perimeter = 0.0; for(i = 1; i < nverts ; i++) { for( j = i-1; j >= 0; j--) { dvx = vx[j] - vx[i]; dvy = vy[j] - vy[i]; len[i][j] = len[j][i] = len[j][i+nverts] = len[i][j+nverts] = len[i + nverts][j + nverts] = len[j + nverts][i + nverts] = sqrt(dvx*dvx + dvy*dvy); if((ret = CompInInfo(i, j, vx[i], vy[i], dvx, dvy, len[i][j])) != 0) { return ret; } } dvx = vx[i] - vx[i-1]; dvy = vy[i] - vy[i-1]; perimeter += len[i-1][i]; if(i > 1) { test = dvx*pdvy - dvy*pdvx; if(test < 0.0) { fprintf(stderr, "not convex at vertex %d\n", i); return -11; } } pdvx = dvx; pdvy = dvy; } dvx = vx[0] - vx[nverts-1]; dvy = vy[0] - vy[nverts-1]; test = dvx*pdvy - dvy*pdvx; if(test < 0.0) { fprintf(stderr, "not convex at vertex %d\n", nverts-1); return -11; } pdvx = dvx; pdvy = dvy; dvx = vx[1] - vx[0]; dvy = vy[1] - vy[0]; test = dvx*pdvy - dvy*pdvx; if(test < 0.0) { fprintf(stderr, "not convex at vertex %d\n", 0); return -11; } perimeter += len[0][nverts-1]; for(i = 0; i < nverts ; i++) { test = len[i][(i+1)%nverts] + len[(i+1)%nverts][(i+2)%nverts] + len[i][(i+2)%nverts]; cost[i][i+2] = test; } return 0; } char inbuf[256]; int ParseInput() { int i, n, x, y; if(fgets(&(inbuf[0]), 255, stdin) == NULL) { fprintf(stderr, "read failed on vert count\n"); return -1; } if(sscanf(&(inbuf[0]), "%d", &n) != 1) { fprintf(stderr, "scan failed on vert count\n"); return -2; } if((n < 5) || (n > MAX_VERTS)) { fprintf(stderr, "vert count %d not in range 5 ..%d\n", n, MAX_VERTS); return -3; } nverts = n; for(i = 0; i < n; i++) { if(fgets(&(inbuf[0]), 255, stdin) == NULL) { fprintf(stderr, "read failed on vertex %d\n", i+1); return -4; } if(sscanf(&(inbuf[0]), "%d %d", &x, &y) != 2) { fprintf(stderr, "scan failed on vertex %d\n", i+1); return -5; } vx[i] = (double)x; vy[i] = (double)y; } if(fgets(&(inbuf[0]), 255, stdin) == NULL) { fprintf(stderr, "read failed on son 1 position\n"); return -6; } if(sscanf(&(inbuf[0]), "%d %d", &x, &y) != 2) { fprintf(stderr, "scan failed on son 1 position\n"); return -7; } px1 = (double)x; py1 = (double)y; if(fgets(&(inbuf[0]), 255, stdin) == NULL) { fprintf(stderr, "read failed on son 2 position\n"); return -8; } if(sscanf(&(inbuf[0]), "%d %d", &x, &y) != 2) { fprintf(stderr, "scan failed on son 2 position\n"); return -9; } px2 = (double)x; py2 = (double)y; pvx = px2 - px1; pvy = py2 - py1; return 0; } int main() { int ret; double dret; if((ret = ParseInput()) != 0) { return ret; } if((ret = ProcessPoints()) != 0) { if(ret == LINE_THRU_PT) { printf("IMPOSSIBLE\n"); return 0; } return ret; } dret = FindMinCost(); if(dret == BIG) { printf("IMPOSSIBLE\n"); } else { dret = 0.5*(dret - perimeter); printf("%lf\n", dret); } return 0; }