#include using namespace std; const long long INF = 1LL<<50; typedef long long LL; class Point { public: LL x, y; Point(LL _x=0, LL _y=0) : x(_x), y(_y) {} Point operator+(const Point p) { return Point(x+p.x, y+p.y); } Point operator-(const Point p) { return Point(x-p.x, y-p.y); } LL operator*(const Point p) { return x*p.x+y*p.y; } Point operator*(const LL k) { return Point(x*k, y*k); } LL operator^(const Point p) { return x*p.y-y*p.x; } Point& operator=(const Point p) { x=p.x; y=p.y; return *this; } }; LL comparea(Point a, Point b, Point c, Point d) { LL t = a.x*b.y + b.x*c.y + c.x*d.y + d.x*a.y - a.y*b.x - b.y*c.x - c.y*d.x - d.y*a.x; return abs(t); } LL comparea3(Point a, Point b, Point c) { return comparea(a, b, c, c); } LL mygcd(LL x, LL y) { while(x!=0) { y%=x; swap(x, y); } return x+y; } LL solve(Point u, Point v, Point A, Point B) { Point C = v-u; //printf("ask u=(%lld, %lld), v=(%lld, %lld), A=(%lld, %lld), B=(%lld, %lld)\n", u.x, u.y, v.x, v.y, A.x, A.y, B.x, B.y); LL g = mygcd(abs(A.x), abs(A.y)); A.x/=g;A.y/=g; LL gg = mygcd(abs(B.x), abs(B.y)); B.x/=gg;B.y/=gg; //printf(" A=%lld %lld, B=%lld, %lld\n", A.x, A.y, B.x, B.y); if ((A^B) > 0) return INF; if ((A^B) == 0) { // use Pick's theorem. LL area = comparea(u, v, v+A, u+A); if (area + 2 == 2 + 2) return 0; else return INF; } LL delta = (B^A); LL dS = (B^C); // s = dS/delta LL dT = (A^C); // t = dT/delta if (dS%delta==0) { A = A * (dS/delta); B = B * (dT/delta); //printf(" dS=%lld, dT=%lld, delta=%lld\n", dS, dT, delta); //printf(" %lld %lld\n", (u+A).x, (u+A).y); assert(dS%delta==0 && dT%delta==0); assert((u+A).x==(v+B).x && (u+A).y == (v+B).y); Point w = u + A; // use Pick's theorem. LL area = comparea3(u, v, w); // printf(" area = %lld\n", area); LL inside = area + 2 - mygcd(abs(C.x), abs(C.y)) - abs(dS/delta) - abs(dT/delta); assert(inside%2==0 && inside >= 0); inside/=2; return inside; } // bruteforce double ux=u.x; double uy=u.y; double vx=v.x; double vy=v.y; double wx=u.x + A.x * dS / (double)delta; double wy=u.y + A.y * dS / (double)delta; LL miny = ceill(min(uy, min(vy, wy))); LL maxy = floorl(max(uy, max(vy, wy))); LL total=0; for (LL y = miny; y <= maxy; y++) { if (C.y==0 && u.y==y) continue; if (A.y==0 && u.y==y) continue; if (B.y==0 && v.y==y) continue; vector xs; const double eps=1e-9; if (min(uy, vy)-eps <= y && y <= max(uy, vy)+eps) { xs.push_back(ux + (vx-ux)*(y-uy)/(vy-uy)); } if (min(vy, wy)-eps <= y && y <= max(vy, wy)+eps) { xs.push_back(vx + (wx-vx)*(y-vy)/(wy-vy)); } if (min(wy, uy)-eps <= y && y <= max(wy, uy)+eps) { xs.push_back(wx + (ux-wx)*(y-wy)/(uy-wy)); } assert(xs.size()>=2); sort(xs.begin(), xs.end()); LL vq = floorl(xs.back()-eps) - ceill(xs[0]+eps) + 1; // printf(" y=%d; vq =%lld; ", (int)y, vq); for (double x : xs) printf("%.3f ", x); puts(""); total += max(0LL, vq); } return total; } int main() { int n; scanf("%d", &n); vector a(2*n); for (int i = 0; i < n; i++) { scanf("%lld%lld", &a[i].x, &a[i].y); a[i+n] = a[i]; } LL answer = 0; for(int i=1;i<=n;i++) { LL t = solve(a[i], a[i+1], a[i]-a[i-1], a[i+1]-a[i+2]); if (t == INF) { puts("infinitely many"); return 0; } // printf("t=%lld\n", t); answer += t; } printf("%d\n", answer); return 0; }