#include #include #include #include #include //#define DEBUG // print all triples found, labelling duplicates //#define DEBUG1 // print a message if no element of a triple is the input value typedef unsigned long DWORD; typedef unsigned short WORD; typedef unsigned char BYTE; #ifndef WIN32 typedef unsigned long long DDWORD; typedef long long LLONG; #else typedef unsigned __int64 DDWORD; typedef __int64 LLONG; #endif int inverts[50][2]; int convverts[60][2]; int edgevects[60][2]; // move input to extended array, other ends copied // and compute edge vector int ProcessInput(int npts) { int i; for(i = 0; i < npts ; i++) { convverts[i+1][0] = inverts[i][0]; convverts[i+1][1] = inverts[i][1]; } convverts[0][0] = convverts[npts][0]; convverts[0][1] = convverts[npts][1]; convverts[npts+1][0] = convverts[1][0]; convverts[npts+1][1] = convverts[1][1]; convverts[npts+2][0] = convverts[2][0]; convverts[npts+2][1] = convverts[2][1]; for(i = 0; i < npts+2; i++) { edgevects[i][0] = convverts[i+1][0] - convverts[i][0]; edgevects[i][1] = convverts[i+1][1] - convverts[i][1]; } return 0; } // check that input points are define a convex hull traversed counter-clockwise (return -1 if not) // and check if there are infinitrly many extenion points (return 1 only if it is convex)) // else return 0 int CheckConvInfinite(int npts) { int i, cross1, cross2, inf, paracnt; inf = paracnt = 0; for(i = 0; i < npts ; i++) { cross1 = edgevects[i][0]* edgevects[i+1][1] - edgevects[i][1]* edgevects[i+1][0]; cross2 = edgevects[i][0]* edgevects[i+2][1] - edgevects[i][1]* edgevects[i+2][0]; if(cross1 <= 0) return -1; if(cross2 < 0) inf = 1; else if(cross2 == 0) paracnt++; } if(npts == 4) { if((paracnt == 4) && (cross1 == 1)) { return 2; } else { return 1; } } if((inf > 0) || (paracnt > 0)) { return 1; } return 0; } LLONG GCD(LLONG a, LLONG b) { LLONG c; a = a >= 0 ? a : -a; b = b>= 0 ? b : -b; if(a == 0) return b; if(b == 0) return a; c = a%b; while(c != 0) { a = b; b = c; c = a%b; } return b; } // if the intersection coodinates use Pick's theorem to find the number of solution points LLONG FindPickIntpts(int *p1, int *p2, LLONG *p3) { LLONG ret, dx12, dy12, dx13, dy13, dx23, dy23, a2, b; dx12 = p2[0] - p1[0]; dy12 = p2[1] - p1[1]; dx13 = p3[0] - p1[0]; dy13 = p3[1] - p1[1]; dx23 = p3[0] - p2[0]; dy23 = p3[1] - p2[1]; a2 = (dx12*dy13 - dx13*dy12); if(a2 < 0) a2 = -a2; b = GCD(dx12, dy12) + GCD(dx13, dy13) + GCD(dx23, dy23); ret = a2 - b; if ((ret & 1) != 0) { return -1; } else { return ((ret/2) + 1); } } // eqn of extnsion of(v(i-1)->v(i)) = p1 + v1*t // eqn of extnsion of(v(i+1)->v(i+2)) = p2 - v2*s (v2 pts wrong dir) // solving: v1*t + v2*s = p2 - p1 // v1[0] t + v2[0] s = p2[0] - p1[0] // v1[1] t + v2[1] s = p2[1] - p1[1] // check if third vertex has integer coodinates (return 1 with coors in ires // else find double coords int FindThirdVert(int *p1, int*v1, int*p2, int*v2, double *res, LLONG *ires) { LLONG den, numt, rhs[2]; int ret; rhs[0] = p2[0] - p1[0]; rhs[1] = p2[1] - p1[1]; den = v1[0]*v2[1] - v2[0]*v1[1]; ret = 0; if(den == 0) { // lines are parallel return -1; } numt = rhs[0]*v2[1] - v2[0]*rhs[1]; if(((numt*v1[0])%den == 0) && ((numt*v1[1])%den == 0)) { ires[0] = ((numt*v1[0])/den) + p1[0]; ires[1] = ((numt*v1[1])/den) + p1[1]; ret = 1; } res[0] = (double)p1[0] + (((double)numt)*((double)v1[0]))/((double)den); res[1] = (double)p1[1] + (((double)numt)*((double)v1[1]))/((double)den); return ret; } #define EPS (.0000005) // use doubles to scan the riangle to find the number of solution points // lots of cases DDWORD CountIntTriPtsF(int *p1, int*v1, int*p2, int*v2, int ind) { double x1, y1, x2, y2, x3, y3, dxL1, dxR1, dxL2, dxR2, xL, xR, tx, fudge; int ixl, ixr, y, ymid, ybot, ytop, ret, iyl; double res[2], yfudge; LLONG pret, p3[2]; DDWORD ddret; ret = FindThirdVert(p1, v1, p2, v2, &res[0], &p3[0]); pret = -1; if(ret == 1) { // if third vert is integer can use Pick to compute and return pret = FindPickIntpts(p1, p2, &p3[0]); #ifndef DEBUG // mostly used for debugging if(pret >= 0) { return pret; } #endif } x3 = res[0]; y3 = res[1]; x1 = p1[0], y1 = p1[1], x2 = p2[0], y2 = p2[1]; // since (int)double truncates toward zero and I want to trunc left (down) // add a fudge factor to all points to force all x'x to be > 0 if(x1 < x2) tx = x1; else tx = x2; if(x3 < tx) tx = x3; fudge = 2.0; if(tx < 0.0) { ixl = (int)tx; fudge -= (double)ixl; } //same for y's if(y1 < y2) tx = y1; else tx = y2; if(y3 < tx) tx = y3; iyl = 2; if(tx < 0.0) { ixl = (int)tx; iyl -= ixl; } yfudge = (double)iyl; ddret = 0; if((y3 > y1+EPS) && (y3 > y2+EPS)) { ytop = (int)(y3 +yfudge - EPS) - iyl; if(p1[1] == p2[1]) { //y3 > y1 = y2 scan up y = p1[1]; if(x1 < x2) { xL = x1; xR = x2; dxL1 = (x3 - x1)/(y3 - y1); dxR1 = (x3 - x2)/(y3- y2); } else { xR = x1; xL = x2; dxR1 = (x3 - x1)/(y3 - y1); dxL1 = (x3 - x2)/(y3- y2); } xL += fudge; xR += fudge; while(y < ytop) { y++; xL += dxL1; xR += dxR1; ixl = (int)(xL + EPS) + 1; ixr = (int)(xR - EPS); ddret += ixr - ixl + 1; } } else if(p1[1] < p2[1]) { // y3 > y2 > y1 scan up y1 to y2 then up y2 to y3 ymid = p2[1]; y = p1[1]; if(x1 < x2) { dxL1 = dxL2 = (x3 - x1)/(y3 - y1); dxR2 = (x3 - x2)/(y3 - y2); dxR1 = (x2 - x1)/(y2 - y1); } else{ dxR1 = dxR2 = (x3 - x1)/(y3 - y1); dxL2 = (x3 - x2)/(y3 - y2); dxL1 = (x2 - x1)/(y2 - y1); } xL = xR = x1 + fudge; while(y < ymid) { y++; xL += dxL1; xR += dxR1; ixl = (int)(xL + EPS) + 1; ixr = (int)(xR - EPS); ddret += ixr - ixl + 1; } while(y < ytop) { y++; xL += dxL2; xR += dxR2; ixl = (int)(xL + EPS) + 1; ixr = (int)(xR - EPS); ddret += ixr - ixl + 1; } } else { // y3 > y1 > y2 scan up y2 to y1 then up y1 to y3 ymid = p1[1]; y = p2[1]; if(x1 > x2) { dxL1 = dxL2 = (x3 - x2)/(y3 - y2); dxR2 = (x3 - x1)/(y3 - y1); dxR1 = (x1 - x2)/(y1 - y2); } else{ dxR1 = dxR2 = (x3 - x2)/(y3 - y2); dxL2 = (x3 - x1)/(y3 - y1); dxL1 = (x1 - x2)/(y1 - y2); } xL = xR = x2 + fudge; while(y < ymid) { y++; xL += dxL1; xR += dxR1; ixl = (int)(xL + EPS) + 1; ixr = (int)(xR - EPS); ddret += ixr - ixl + 1; } while(y < ytop) { y++; xL += dxL2; xR += dxR2; ixl = (int)(xL + EPS) + 1; ixr = (int)(xR - EPS); ddret += ixr - ixl + 1; } } } else if((y3 < y1-EPS) && (y3 < y2-EPS)) { ybot = (int)(y3 + yfudge + EPS) + 1 - iyl; if(p1[1] == p2[1]) { // y1 = y1 > y3 scan down to y3 y = p1[1]; if(x1 < x2) { xL = x1; xR = x2; dxL1 = (x3 - x1)/(y3 - y1); dxR1 = (x3 - x2)/(y3- y2); } else { xR = x1; xL = x2; dxR1 = (x3 - x1)/(y3 - y1); dxL1 = (x3 - x2)/(y3- y2); } xL += fudge; xR += fudge; while(y > ybot) { y--; xL -= dxL1; xR -= dxR1; ixl = (int)(xL + EPS) + 1; ixr = (int)(xR - EPS); ddret += ixr - ixl + 1; } } else if(p1[1] > p2[1]) { // y1 > y2 > y3 scan down y1 to y2 then down y2 to y3 ymid = p2[1]; y = p1[1]; if(x1 < x2) { dxL1 = dxL2 = (x3 - x1)/(y3 - y1); dxR2 = (x3 - x2)/(y3 - y2); dxR1 = (x2 - x1)/(y2 - y1); } else{ dxR1 = dxR2 = (x3 - x1)/(y3 - y1); dxL2 = (x3 - x2)/(y3 - y2); dxL1 = (x2 - x1)/(y2 - y1); } xL = xR = x1 + fudge; while(y > ymid) { y--; xL -= dxL1; xR -= dxR1; ixl = (int)(xL + EPS) + 1; ixr = (int)(xR - EPS); ddret += ixr - ixl + 1; } while(y > ybot) { y--; xL -= dxL2; xR -= dxR2; ixl = (int)(xL + EPS) + 1; ixr = (int)(xR - EPS); ddret += ixr - ixl + 1; } } else { // y2 > y1 > y3 scan down y2 to y1 then down y1 to y3 ymid = p1[1]; y = p2[1]; if(x1 > x2) { dxL1 = dxL2 = (x3 - x2)/(y3 - y2); dxR2 = (x3 - x1)/(y3 - y1); dxR1 = (x1 - x2)/(y1 - y2); } else{ dxR1 = dxR2 = (x3 - x2)/(y3 - y2); dxL2 = (x3 - x1)/(y3 - y1); dxL1 = (x1 - x2)/(y1 - y2); } xL = xR = x2 + fudge; while(y > ymid) { y--; xL -= dxL1; xR -= dxR1; ixl = (int)(xL + EPS) + 1; ixr = (int)(xR - EPS); ddret += ixr - ixl + 1; } while(y > ybot) { y--; xL -= dxL2; xR -= dxR2; ixl = (int)(xL + EPS) + 1; ixr = (int)(xR - EPS); ddret += ixr - ixl + 1; } } } else if(p1[1] > p2[1]){ // y1 >= y3 >= y2 if(fabs(y1 - y3) < EPS) { // y1 = y3 > y2 scan up form y2 to y1,y3 y = p2[1]; if(x1 < x3) { xL = xR = x2; dxL1 = (x1 - x2)/(y1 - y2); dxR1 = (x3 - x2)/(y3- y2); } else { xR = xL = x2; dxL1 = (x3 - x2)/(y3 - y2); dxR1 = (x1 - x2)/(y1- y2); } xL += fudge; xR += fudge; ytop = p1[1] - 1; while(y < ytop) { y++; xL += dxL1; xR += dxR1; ixl = (int)(xL + EPS) + 1; ixr = (int)(xR - EPS); ddret += ixr - ixl + 1; } } else if(fabs(y2 - y3) < EPS) { // y1 > y2 = y3 scan down from y1 to y2,y3 y = p1[1]; if(x2 < x3) { xL = xR = x1; dxL1 = (x1 - x2)/(y1 - y2); dxR1 = (x3 - x1)/(y3- y1); } else { xR = xL = x1; dxL1 = (x3 - x1)/(y3 - y1); dxR1 = (x1 - x2)/(y1- y2); } xL += fudge; xR += fudge; ytop = p2[1] + 1; while(y > ytop) { y--; xL -= dxL1; xR -= dxR1; ixl = (int)(xL + EPS) + 1; ixr = (int)(xR - EPS); ddret += ixr - ixl + 1; } } else { // y1 > y3 > y2 scan down from y1 to (int)y3 +1 then up from y2 to (int)y3 // what is x on 1->2 at y3 tx = x1 + (x1 - x2)*(y3 - y1)/(y1 - y2); ytop = (int)(y3 + yfudge) - iyl; ybot = ytop+1; if(tx < x3) { dxL1 = dxL2 = (x1 - x2)/(y1 - y2); dxR1 = (x1 - x3)/(y1 - y3); dxR2 = (x2 - x3)/(y2 - y3); } else { dxR1 = dxR2 = (x1 - x2)/(y1 - y2); dxL1 = (x1 - x3)/(y1 - y3); dxL2 = (x2 - x3)/(y2 - y3); } y = p1[1]; xL = xR = x1 + fudge; while(y > ybot) { y--; xL -= dxL1; xR -= dxR1; ixl = (int)(xL + EPS) + 1; ixr = (int)(xR - EPS); ddret += ixr - ixl + 1; } y = p2[1]; xL = xR = x2 + fudge; while(y < ytop) { y++; xL += dxL2; xR += dxR2; ixl = (int)(xL + EPS) + 1; ixr = (int)(xR - EPS); ddret += ixr - ixl + 1; } } } else { // y2 >= y3 >= y1 if(fabs(y1 - y3) < EPS) { // y2 > y1 = y3 scna down from y2 to y1,y3 y = p2[1]; if(x1 < x3) { xL = xR = x2; dxL1 = (x1 - x2)/(y1 - y2); dxR1 = (x3 - x2)/(y3- y2); } else { xR = xL = x2; dxL1 = (x3 - x2)/(y3 - y2); dxR1 = (x1 - x2)/(y1- y2); } xL += fudge; xR += fudge; ybot = p1[1] + 1; while(y > ybot) { y--; xL -= dxL1; xR -= dxR1; ixl = (int)(xL + EPS) + 1; ixr = (int)(xR - EPS); ddret += ixr - ixl + 1; } } else if(fabs(y2 - y3) < EPS) { // y2 = y3 > y1 scan up from y1 to y2,y3 y = p1[1]; if(x2 < x3) { xL = xR = x1; dxL1 = (x1 - x2)/(y1 - y2); dxR1 = (x3 - x1)/(y3- y1); } else { xR = xL = x1; dxL1 = (x3 - x1)/(y3 - y1); dxR1 = (x1 - x2)/(y1- y2); } xL += fudge; xR += fudge; ytop = p2[1] - 1; while(y < ytop) { y++; xL += dxL1; xR += dxR1; ixl = (int)(xL + EPS) + 1; ixr = (int)(xR - EPS); ddret += ixr - ixl + 1; } } else { // y2 > y3 > y1 scan down from y2 to (int)y3 + 1 then up from y1 to (int)y3 // what is x on 1->2 at y3 tx = (x1 - x2)*(y3 - y1); tx /= (y1 - y2); tx += x1; ytop = (int)(y3 + yfudge) - iyl; ybot = ytop+1; if(tx < x3) { dxL1 = dxL2 = (x1 - x2)/(y1 - y2); dxR1 = (x1 - x3)/(y1 - y3); dxR2 = (x2 - x3)/(y2 - y3); } else { dxR1 = dxR2 = (x1 - x2)/(y1 - y2); dxL1 = (x1 - x3)/(y1 - y3); dxL2 = (x2 - x3)/(y2 - y3); } xL = xR = x2 + fudge; y = p2[1]; while(y > ybot) { y--; xL -= dxL2; xR -= dxR2; ixl = (int)(xL + EPS) + 1; ixr = (int)(xR - EPS); ddret += ixr - ixl + 1; } xL = xR = x1 + fudge; y = p1[1]; while(y < ytop) { y++; xL += dxL1; xR += dxR1; ixl = (int)(xL + EPS) + 1; ixr = (int)(xR - EPS); ddret += ixr - ixl + 1; } } } #ifdef DEBUG if((pret >= 0) && ((unsigned)pret != ddret)) { printf("%d: pret %d ddddret %d\n", ind, pret, ddret); } #endif return ddret; } // for each side of convex hull find the number of soluiuton bounded by this side // and the previous and next sodes extended and sum them DDWORD CountExtPts(int npts) { int i; DDWORD sum = 0; for(i = 1; i <= npts; i++) { sum += CountIntTriPtsF(&(convverts[i][0]), &(edgevects[i-1][0]), &(convverts[i+1][0]), &(edgevects[i+1][0]), i); } return sum; } char inbuf[256]; int main() { int ret, npts, i, x, y; DDWORD lret; if(fgets(&(inbuf[0]), 255, stdin) == NULL) { fprintf(stderr, "read failed on num points\n"); return -1; } if(sscanf(&(inbuf[0]), "%d", &npts) != 1) { fprintf(stderr, "scan failed on input\n"); return -2; } if((npts < 3) || (npts > 50)) { fprintf(stderr, "npts %d not in range 3 ... 50\n", npts); return -3; } for(i = 0 ; i < npts ; i++) { if(fgets(&(inbuf[0]), 255, stdin) == NULL) { fprintf(stderr, "read failed on point %d\n", i+1); return -4; } if(sscanf(&(inbuf[0]), "%d %d", &x, &y) != 2) { fprintf(stderr, "scan failed on point %d\n", i+1); return -5; } if((x < -1000) || (x > 1000) || (y < -1000) || (y > 1000)) { fprintf(stderr, "point %d x %d or y %d not in range -1000 ... 1000\n", i+1, x, y); return -6; } inverts[i][0] = x; inverts[i][1] = y; } ProcessInput(npts); if(npts == 3) { printf("infinitely many\n"); return 0; } ret = CheckConvInfinite(npts); if(ret < 0) { fprintf(stderr, "not convex hull\n"); return -7; } else if (ret == 1) { printf("infinitely many\n"); } else if(ret == 2) { printf("0\n"); } else { lret = CountExtPts(npts); #ifndef WIN32 printf("%llu\n", lret); #else printf("%I64u\n", lret); #endif } return 0; }