#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); if (top > bot) bot += nverts; *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, i1, j1; double cur, ret, prevret; ret = prevret = BIG; for (i = 0; i < nverts - 1; i++) { if (InCount[i] < 2) { continue; } if (FindTopBottom(i, &top, &bot) != 0) { continue; } for (j1 = bot; j1 > top; j1--) { for (i1 = top; i1 < j1; i1++) { cur = len[i][i1] + len[i][j1] + len[i1][j1]; j = i1; if (j < i) j += nverts; k = i; if (k < j1) k += nverts; m = j1; if (m < i1) m += nverts; cur += FindCost(i, j); cur += FindCost(j1, k); cur += FindCost(i1, m); if (cur < ret) ret = cur; } } if(ret = 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; }