#include<bits/stdc++.h>

#define cp const point &
#define cl const line &
#define cc const circle &
#define LD long double
std::mt19937 rnd(time(0));
const LD eps = 1e-8;
const LD pi = std::numbers::pi;
const LD INF = 1e9;

int sgn(LD x)
{
    return x > eps ? 1 : (x < -eps ? -1 : 0);
}

LD sqr(LD x)
{ return x * x; }

struct point
{
    LD x, y;

    point operator+(cp a) const
    { return {x + a.x, y + a.y}; }

    point operator-(cp a) const
    { return {x - a.x, y - a.y}; }

    point operator*(LD t) const
    { return {x * t, y * t}; }

    point operator/(LD t) const
    { return {x / t, y / t}; }

    point rot(LD t) const
    { return {(LD) (x * cos(t) - y * sin(t)), (LD) (x * sin(t) + y * cos(t))}; }

    point rot90() const
    { return {-y, x}; }

    LD len2() const
    { return x * x + y * y; }

    LD len() const
    { return sqrtl(x * x + y * y); }

    point unit() const
    {
        LD d = len();
        return {(LD) (x / d), (LD) (y / d)};
    }

    int on_up()//b不判（0,0）
    {
        return sgn(y) == 1 || (sgn(y) == 0 && sgn(x) < 0);
    }

    void print()
    {
        std::cout << x << ' ' << y << std::endl;
    }

    void read()
    {
        int xx, yy;
        std::cin >> xx >> yy;
        x = xx, y = yy;
    }

    friend bool operator<(cp a, cp b)
    {
        return a.x == b.x ? a.y < b.y : a.x < b.x;
    }

    friend bool operator>(cp a, cp b)
    {
        return a.x == b.x ? a.y > b.y : a.x > b.x;
    }
};

LD dot(cp a, cp b);

bool operator==(cp a, cp b)
{
    return !sgn(dot(a - b, a - b));
//    return !sgn(a.x-b.x)&&!(a.y-b.y);看题目
}

LD dis(cp a, cp b)//两点距离
{
    return sqrtl(sqr(a.x - b.x) + sqr(a.y - b.y));
}

LD dot(cp a, cp b)//点乘
{
    return a.x * b.x + a.y * b.y;
}

LD det(cp a, cp b)//叉乘
{
    return a.x * b.y - b.x * a.y;
}

bool turn_left(cp a, cp b, cp c)//判断ba是否逆时针转少于180°到ca
{
    return sgn(det(b - a, c - a)) > 0;//大于是严格凸包
}

struct line
{
    point s, t;

    line()
    {}

    line(point a, point b) : s(a), t(b)
    {}

    void read()
    {
        s.read(), t.read();
    }

    void print()
    {
        s.print(), std::cout << ' ', t.print();
    }

};

struct circle
{
    point c;
    LD r;

    circle()
    {}

    circle(point C, LD R)
    { c = C, r = R; }
};

bool in_circle(cp a, cc b)
{
    return sgn((b.c - a).len() - b.r) <= 0;
}

circle make_circle(point u, point v)
{
    point p = (u + v) / 2;
    return circle(p, (u - p).len());
}

circle make_circle(cp a, cp b, cp c)
{
    point p = b - a, q = c - a;
    point s(dot(p, p) / 2, dot(q, q) / 2);
    LD d = det(p, q);
    p = point(det(s, point(p.y, q.y)), det(point(p.x, q.x), s)) / d;
    return circle(a + p, p.len());
}

circle min_circle(std::vector<point> p)
{
    circle ret(p[0], 0);
    std::shuffle(p.begin(), p.end(), rnd);
    int len = p.size();
    for (int i = 0; i < len; i++)
        if (!in_circle(p[i], ret))
        {
            ret = circle(p[i], 0);
            for (int j = 0; j < i; j++)
                if (!in_circle(p[j], ret))
                {
                    ret = make_circle(p[j], p[i]);
                    for (int k = 0; k < j; ++k)
                        if (!in_circle(p[k], ret))
                            ret = make_circle(p[i], p[j], p[k]);
                }
        }
    return ret;
}

LD get_rad(point a, point b)
{
    if (a == point(0, 0) || b == point(0, 0))
        return 0;
    else
    {
        return acosl(dot(a, b) / (a.len() * b.len()));
    }
}

bool same_dir(cl a, cl b)//判断方向是否一致
{
    return sgn(det(b.t - b.s, a.t - a.s)) == 0 && sgn(dot(b.t - b.s, a.t - a.s)) > 0;
}

bool point_on_line(cp a, cl l)//判断点是否在直线上
{
    return sgn(det(a - l.s, l.t - l.s)) == 0;
}

bool point_on_segment(cp a, cl l)//判断点是否在线段上
{
    return point_on_line(a, l) && sgn(dot(l.s - a, l.t - a)) <= 0;//(<=代表可以端点
}

bool two_side(cp a, cp b, cl c)//判断两个点是否在线段的两边
{
    return sgn(det(a - c.s, c.t - c.s)) * sgn(det(b - c.s, c.t - c.s)) < 0;
}

bool intersect_judge_strict(cl a, cl b)
{
    return two_side(a.s, a.t, b) && two_side(b.s, b.t, a);
}

bool intersect_judge(cl a, cl b)
{//判断两个线段是否相交
    if (point_on_segment(a.s, b) || point_on_segment(a.t, b) || point_on_segment(b.s, a) ||
        point_on_segment(b.t, a))
        return true;
    return intersect_judge_strict(a, b);
}


point line_intersect(cl a, cl b)
{//得到两线段的交点
    LD s1 = det(a.t - a.s, b.s - a.s);
    LD s2 = det(a.t - a.s, b.t - a.s);
    return (b.s * s2 - b.t * s1) / (s2 - s1);
}

bool point_on_ray(cp a, cl b)
{//判断点是否在射线上
    return sgn(det(a - b.s, b.t - b.s)) == 0 && sgn(dot(a - b.s, b.t - b.s)) >= 0;
}

bool ray_intersect_judge(line a, line b)//判断两射线是否相交
{
    LD s1, s2;
    s1 = det(a.t - a.s, b.s - a.s);
    s2 = det(a.t - a.s, b.t - a.s);
    if (sgn(s1) == 0 && sgn(s2) == 0)
        return sgn(dot(a.t - a.s, b.s - a.s)) >= 0 || sgn(dot(b.t - b.s, a.s - b.s));
    if (!sgn(s1 - s2) || sgn(s1) == sgn(s2 - s1))return 0;
    std::swap(a, b);
    s1 = det(a.t - a.s, b.s - a.s);
    s2 = det(a.t - a.s, b.t - a.s);
    return sgn(s1) != sgn(s2 - s1);
}

LD point_to_line(cp a, cl b)
{//点到直线的距离
    return abs(det(b.t - b.s, a - b.s)) / dis(b.s, b.t);
}

point project_to_line(cp a, cl b)
{//得到点在线上的投影
    return b.s + (b.t - b.s) * (dot(a - b.s, b.t - b.s) / (b.t - b.s).len2());
}

LD point_to_segment(cp a, cl b)
{//点到线段的距离
    if (b.s == b.t)
        return dis(a, b.s);
    if (sgn(dot(b.s - a, b.t - b.s)) * sgn(dot(b.t - a, b.t - b.s)) <= 0)
        return abs(det(b.t - b.s, a - b.s)) / dis(b.s, b.t);
    return std::min(dis(a, b.s), dis(a, b.t));
}

std::vector<point> line_circle_intersect(cl a, cc b)//线与圆的交点
{//返回线与圆的交点
    if (sgn(point_to_segment(b.c, a) - b.r) > 0)
        return std::vector<point>();
    LD x = sqrtl(sqr(b.r) - sqr(point_to_line(b.c, a)));
    return std::vector<point>(
            {project_to_line(b.c, a) + (a.s - a.t).unit() * x, project_to_line(b.c, a) - (a.s - a.t).unit() * x});
}

LD circle_intersect_area(cc a, cc b)//求两个圆相交区域的面积
{
    LD d = dis(a.c, b.c);
    if (sgn(d - (a.r + b.r)) >= 0)return 0;
    if (sgn(d - abs(a.r - b.r)) <= 0)
    {
        LD r = std::min(a.r, b.r);
        return r * r * pi;
    }
    LD x = (d * d + a.r * a.r - b.r * b.r) / (2 * d),
            t1 = acosl(std::min((LD) 1, std::max((LD) -1, x / a.r))),
            t2 = acosl(std::min((LD) 1, std::max((LD) -1, (d - x) / b.r)));
    return sqr(a.r) * t1 + sqr(b.r) * t2 - d * a.r * sinl(t1);
}

std::vector<point> circle_intersect(cc a, cc b)//求两个圆的交
{
    if (a.c == b.c || sgn(dis(a.c, b.c) - a.r - b.r) > 0 || sgn(dis(a.c, b.c) - abs(a.r - b.r)) < 0)
        return {};
    point r = (b.c - a.c).unit();
    LD d = dis(a.c, b.c);
    LD x = ((sqr(a.r) - sqr(b.r)) / d + d) / 2;
    LD h = sqrtl(sqr(a.r) - sqr(x));
    if (sgn(h) == 0)return {a.c + r * x};
    return {a.c + r * x + r.rot90() * h, a.c + r * x - r.rot90() * h};
}

std::vector<point> tangent(cp a, cc b)//求一个点关于圆的切线
{
    circle p = make_circle(a, b.c);
    return circle_intersect(p, b);
}

std::vector<line> extangent(cc a, cc b)//求两圆的外切线
{
    std::vector<line> ret;
    if (sgn(dis(a.c, b.c) - abs(a.r - b.r)) <= 0)return ret;
    if (sgn(a.r - b.r) == 0)
    {
        point dir = b.c - a.c;
        dir = (dir * a.r / dir.len()).rot90();
        ret.push_back(line(a.c + dir, b.c + dir));
        ret.push_back(line(a.c - dir, b.c - dir));
    }
    else
    {
        point p = (b.c * a.r - a.c * b.r) / (a.r - b.r);
        std::vector pp = tangent(p, a), qq = tangent(p, b);
        if (pp.size() == 2 && qq.size() == 2)
        {
            if (sgn(a.r - b.r) < 0)
                std::swap(pp[0], pp[1]), std::swap(qq[0], qq[1]);
            ret.push_back(line(pp[0], qq[0]));
            ret.push_back(line(pp[1], qq[1]));
        }
    }
    return ret;
}

std::vector<line> intangent(cc a, cc b)//求两圆的内切线
{
    std::vector<line> ret;
    point p = (b.c * a.r + a.c * b.r) / (a.r + b.r);
    std::vector pp = tangent(p, a), qq = tangent(p, b);
    if (pp.size() == 2 && qq.size() == 2)
    {
        ret.push_back(line(pp[0], qq[0]));
        ret.push_back(line(pp[1], qq[1]));
    }
    return ret;
}

std::vector<point> cut(const std::vector<point> &c, line p)
{
    std::vector<point> ret;
    if (c.empty())return ret;
    int len = c.size();
    for (int i = 0; i < len; i++)
    {
        int j = (i + 1) % len;
        if (turn_left(p.s, p.t, c[i]))ret.push_back(c[i]);
        if (two_side(c[i], c[j], p))
            ret.push_back(line_intersect(p, line(c[i], c[j])));
    }
    return ret;
}

std::vector<point> convex_hull(std::vector<point> a)
{//凸包，字典序
    int n = (int) a.size(), cnt = 0;
    if (n < 2) return a;
    std::sort(a.begin(), a.end()); // less<pair>
    std::vector<point> ret;
    for (int i = 0; i < n; ++i)
    {
        while (cnt > 1
               && !turn_left(ret[cnt - 1], a[i], ret[cnt - 2]))
            --cnt, ret.pop_back();
        ++cnt, ret.push_back(a[i]);
    }
    int fixed = cnt;
    for (int i = n - 2; i >= 0; --i)
    {
        while (cnt > fixed
               && !turn_left(ret[cnt - 1], a[i], ret[cnt - 2]))
            --cnt, ret.pop_back();
        ++cnt, ret.push_back(a[i]);
    }
    ret.pop_back();
    return ret;
}

std::vector<point> minkovski(std::vector<std::vector<point>> a)
{
    if (a[0].size() == 1)
        return a[1];
    if (a[1].size() == 1)
        return a[0];
    for (int i = 0; i < 2; i++)a[i].push_back(a[i].front());
    int i[2] = {0, 0}, len[2] = {(int) a[0].size() - 1, (int) a[1].size() - 1};
    std::vector<point> ret;
    ret.push_back(a[0][0] + a[1][0]);
    do
    {
        int d = sgn(det(a[1][i[1] + 1] - a[1][i[1]], a[0][i[0] + 1] - a[0][i[0]])) >= 0;
        ret.push_back(a[d][i[d] + 1] - a[d][i[d]] + ret.back());
        i[d] = (i[d] + 1) % len[d];
    }
    while (i[0] || i[1]);
    return ret;
}

struct Convex
{
    int n;
    std::vector<point> a, upper, lower;
    std::map<point, int> mp;

    Convex(std::vector<point> _a) : a(_a)
    {
        n = a.size();
        int k = 0;
        for (int i = 1; i < n; i++)if (a[k] < a[i])k = i;
        for (int i = 0; i <= k; i++) lower.push_back(a[i]);
        for (int i = k; i < n; i++) upper.push_back(a[i]);
        upper.push_back(a[0]);
    }

    void pre_to_check_point()
    {
        for (int i = 0; i < n; i++)
            mp[a[i]] = i;
    }

    std::pair<LD, int> get_tan(std::vector<point> &con, point vec)
    {
        int l = 0, r = (int) con.size() - 2;
        for (; l + 1 < r;)
        {
            int mid = (l + r) / 2;
            if (sgn(det(con[mid + 1] - con[mid], vec)) > 0)r = mid;
            else l = mid;
        }
        return std::max(std::make_pair(det(vec, con[r]), r), std::make_pair(det(vec, con[0]), 0));
    }

    void upd_tan(cp p, int id, int &i0, int &i1)//辅助函数
    {
//        if (i0 == -1) i0 = id;
        if ((det(a[i0] - p, a[id] - p)) > 0) i0 = id;
//        if (i1 == -1) i1 = id;
        if ((det(a[i1] - p, a[id] - p)) < 0) i1 = id;
    }

    void search(int l, int r, point p, int &i0, int &i1)//辅助函数
    {
        if (l == r)return;
        upd_tan(p, l % n, i0, i1);
        int sl = sgn(det(a[l % n] - p, a[(l + 1) % n] - p));
        for (; l + 1 < r;)
        {
            int mid = (l + r) / 2;
            int smid = sgn(det(a[mid % n] - p, a[(mid + 1) % n] - p));
            if (smid == sl)l = mid;
            else r = mid;
        }
        upd_tan(p, r % n, i0, i1);
    }

    int search(point u, point v, int l, int r)//辅助函数
    {
        int sl = sgn(det(v - u, a[l % n] - u));
        for (; l + 1 < r;)
        {
            int mid = (l + r) / 2;
            int smid = sgn(det(v - u, a[mid % n] - u));
            if (smid == sl) l = mid;
            else r = mid;
        }
        return l % n;
    }

    //判定点是否在凸包内，在边界返回true
    bool contain(point p)
    {
        if (p.x < lower[0].x || p.x > lower.back().x)return false;
        int id = std::lower_bound(lower.begin(), lower.end(), point(p.x, -INF)) - lower.begin();
        if (lower[id].x == p.x)
        {
            if (lower[id].y > p.y)return false;
        }
        else if (det(lower[id - 1] - p, lower[id] - p) < 0)
            return false;
        id = std::lower_bound(upper.begin(), upper.end(), point(p.x, INF), std::greater<point>()) - upper.begin();
        if (upper[id].x == p.x)
        {
            if (upper[id].y < p.y)return false;
        }
        else if (det(upper[id - 1] - p, upper[id] - p) < 0)
            return false;
        return true;
    }

    int contain_strict(point p)//0代表在外面 1代表在里面 2代表在边上 3代表在点上
    {
        if (p.x < lower[0].x || p.x > lower.back().x)return 0;
        int id = std::lower_bound(lower.begin(), lower.end(), point(p.x, -INF)) - lower.begin();
        if (lower[id].x == p.x)
        {
            if (lower[id].y > p.y)return 0;
            else if (sgn(lower[id].y - p.y) == 0) return 3;
            else if (id + 1 < lower.size() && lower[id + 1].x == p.x && p.y < lower[id + 1].y)
                return 2;
            else if (id + 1 < lower.size() && lower[id + 1].x == p.x && p.y == lower[id + 1].y)
                return 3;
        }
        else if (det(lower[id - 1] - p, lower[id] - p) < 0)
            return 0;
        else if (sgn(det(lower[id - 1] - p, lower[id] - p)) == 0)
            return 2;
        id = std::lower_bound(upper.begin(), upper.end(), point(p.x, INF), std::greater<point>()) - upper.begin();
        if (upper[id].x == p.x)
        {
            if (upper[id].y < p.y)return 0;
            else if (upper[id].y == p.y)return 3;
            else if (id + 1 < upper.size() && upper[id + 1].x == p.x && p.y > upper[id + 1].y)
                return 2;
            else if (id + 1 < upper.size() && upper[id + 1].x == p.x && p.y == upper[id + 1].y)
                return 3;
        }
        else if (det(upper[id - 1] - p, upper[id] - p) < 0)
            return 0;
        else if (sgn(det(upper[id - 1] - p, upper[id] - p)) == 0)
            return 2;
        return 1;
    }

    bool get_tan(point p, int &i0, int &i1)
    {// 求点 p 关于凸包的两个切点, 如果在凸包外则有序返回编号, 共线的多个切点返回任意一个, 否则返回 false
        i0 = i1 = 0;
        int id = int(std::lower_bound(lower.begin(), lower.end(), p) - lower.begin());
        search(0, id, p, i0, i1);
        search(id, (int) lower.size(), p, i0, i1);
        id = int(std::lower_bound(upper.begin(), upper.end(), p, std::greater<point>()) - upper.begin());
        search((int) lower.size() - 1, (int) lower.size() - 1 + id, p, i0, i1);
        search((int) lower.size() - 1 + id, (int) lower.size() - 1 + (int) upper.size(), p, i0, i1);
        return true;
    }

    bool my_get_tan(point p, int &i0, int &i1)//自己魔改，常数大,可求点在凸包上的切线
    {
        if (p.x < lower[0].x || p.x > lower.back().x)
        {
            get_tan(p, i0, i1);
            return true;
        }
        int id = std::lower_bound(lower.begin(), lower.end(), point(p.x, -INF)) - lower.begin();
        if (lower[id].x == p.x)
        {
            if (lower[id].y > p.y)
            {
                get_tan(p, i0, i1);
                return true;
            }
            else if (sgn(lower[id].y - p.y) == 0)
            {
                i0 = (id - 1 + n) % n, i1 = (id + 1) % n;
                return true;
            }
            else if (id + 1 < lower.size() && lower[id + 1].x == p.x && p.y < lower[id + 1].y)
            {
                i0 = id, i1 = (id + 1) % n;
                return true;
            }
            else if (id + 1 < lower.size() && lower[id + 1].x == p.x && p.y == lower[id + 1].y)
            {
                i0 = id, i1 = (id + 2) % n;
                return true;
            }
        }
        else if (det(lower[id - 1] - p, lower[id] - p) < 0)
        {
            get_tan(p, i0, i1);
            return true;
        }
        else if (sgn(det(lower[id - 1] - p, lower[id] - p)) == 0)
        {
            i0 = (id - 1 + n) % n, i1 = id;
            return true;
        }
        id = std::lower_bound(upper.begin(), upper.end(), point(p.x, INF), std::greater<point>()) - upper.begin();
        if (upper[id].x == p.x)
        {
            if (upper[id].y < p.y)
            {
                get_tan(p, i0, i1);
                return true;
            }
            else if (upper[id].y == p.y)
            {
                i0 = id + lower.size() - 1;
                i1 = (i0 + 1 + n) % n;
                i0 = (i0 + n - 1) % n;
                return true;
            }
            else if (id + 1 < upper.size() && upper[id + 1].x == p.x && p.y > upper[id + 1].y)
            {
                i0 = id + lower.size() - 1;
                i1 = (i0 + 1) % n;
                i0 = (i0 + n) % n;
                return true;
            }
            else if (id + 1 < upper.size() && upper[id + 1].x == p.x && p.y == upper[id + 1].y)
            {
                i0 = n - 1, i1 = 1;
                return true;
            }
        }
        else if (det(upper[id - 1] - p, upper[id] - p) < 0)
        {
            get_tan(p, i0, i1);
            return true;
        }
        else if (sgn(det(upper[id - 1] - p, upper[id] - p)) == 0)
        {
            i0 = (id + lower.size() - 1 + n) % n;
            i1 = (i0 - 1 + n) % n;
            std::swap(i0, i1);
            return true;
        }
        return false;
    }

    // 求凸包上和向量 vec 叉积最大的点, 返回编号, 共线的多个切点返回任意一个
    int get_tan(point vec)
    {
        std::pair<LD, int> ret = get_tan(upper, vec);
        ret.second = (ret.second + (int) lower.size() - 1) % n;
        ret = std::max(ret, get_tan(lower, vec));
        return ret.second;
    }

    bool my_judge_intersect_segment(cp u, cp v)//判断线段与凸包是否有严格相交，即有无穿过内部,默认起点和终点不在凸包内部了
    {
        int u1, u2;
        my_get_tan(u, u1, u2);
        if (!turn_left(u, a[u2], v) || !turn_left(u, v, a[u1]))
            return false;
        my_get_tan(v, u1, u2);
        if (!turn_left(v, a[u2], u) || !turn_left(v, u, a[u1]))
            return false;
        return true;
    }
    // 求凸包和直线 u,v 的交点, 如果无严格相交返回 false. 如果有则是和 (i,next(i)) 的交点, 两个点无序, 交在点上不确定返回前后两条线段其中之一

    bool get_inter(point u, point v, int &i0, int &i1)
    {
        int p0 = get_tan(u - v), p1 = get_tan(v - u);
        if (sgn(det(v - u, a[p0] - u)) * sgn(det(v - u, a[p1] - u)) < 0)
        {
            if (p0 > p1)std::swap(p0, p1);
            i0 = search(u, v, p0, p1);
            i1 = search(u, v, p1, p0 + n);
            return true;
        }
        else return false;
    }
};

bool in_polygon(cp p, const std::vector<point> &po)//判断点是否在多边形里
{
    int n = (int) po.size();
    int cnt = 0;
    for (int i = 0; i < n; i++)
    {
        point a = po[i], b = po[(i + 1) % n];
        if (point_on_segment(p, line(a, b)))return true;
        int x = sgn(det(p - a, b - a)), y = sgn(a.y - p.y), z = sgn(b.y - p.y);
        if (x > 0 && y <= 0 && z > 0)++cnt;
        if (x < 0 && z <= 0 && y > 0)--cnt;

    }
    return cnt != 0;
}

bool In_Polygon(cp P, std::vector<point> &polygon)//判断点是否在多边形里面，射线法O(n)
{
    bool flag = false; //相当于计数
    point P1, P2; //多边形一条边的两个顶点
    int n = polygon.size();
    for (int i = 0, j = n - 1; i < n; j = i++)
    {
        //polygon[]是给出多边形的顶点
        P1 = polygon[i];
        P2 = polygon[j];
        if (point_on_segment(P, line(P1, P2)))return true;
        //前一个判断min(P1.y,P2.y)<P.y<=max(P1.y,P2.y)
        //这个判断代码我觉得写的很精妙 我网上看的 应该是大神模版
        //后一个判断被测点 在 射线与边交点 的左边
        if ((sgn(P1.y - P.y) > 0 != sgn(P2.y - P.y) > 0) &&
            sgn(P.x - (P.y - P1.y) * (P1.x - P2.x) / (P1.y - P2.y) - P1.x) < 0)
            flag = !flag;
    }
    return flag;
}

std::vector<point> Minkovski(std::vector<std::vector<point>> a)//可处理退化成线段的凸包
{                                                            //闵可夫斯基和
    std::vector<point> S;
    int n = a[0].size(), m = a[1].size();
    std::vector<point> A(n), B(m);
    for (int i = 0; i < n - 1; i++) A[i] = a[0][i + 1] - a[0][i];
    A[n - 1] = a[0][0] - a[0][n - 1];
    for (int i = 0; i < m - 1; i++) B[i] = a[1][i + 1] - a[1][i];
    B[m - 1] = a[1][0] - a[1][m - 1];                                                             //将两个凸包上的边向量都存入a,b中
    S.push_back(a[0][0] + a[1][0]);
    int p1 = 0, p2 = 0;
    while (p1 < n && p2 < m)
    {
        LD d = det(A[p1], B[p2]);
        if (d > 0)
            S.push_back(S.back() + A[p1++]);
        else if (d < 0)
            S.push_back(S.back() + B[p2++]);
        else
        {
            if (dot(A[p1], B[p1]) >= 0)
                S.push_back(S.back() + A[p1++]);
            else
            {
                auto [x, y] = A[p1];
                if (x > 0)
                    S.push_back(S.back() + A[p1++]);
                else if (x < 0)
                    S.push_back(S.back() + B[p2++]);
                else
                {
                    if (y > 0)
                        S.push_back(S.back() + A[p1++]);
                    else S.push_back(S.back() + B[p2++]);
                }
            }
        }
    }
    while (p1 < n)
        S.push_back(S.back() + A[p1++]);
    while (p2 < m)
        S.push_back(S.back() + B[p2++]);
    return S;
}

LD farthest_pair(std::vector<point> pu)//最远点对
{
    pu = convex_hull(pu);
    std::vector<std::vector<point>> ppu(2);
    std::vector<point> pu1;
    for (auto x: pu)
        pu1.push_back(x * -1);
    pu1 = convex_hull(pu1);
    ppu[0] = pu, ppu[1] = pu1;
    auto ret = Minkovski(ppu);
    LD ans = 0;
    for (auto x: ret)
        ans = std::max(ans, x.len());
    return ans;
}

LD closest_pair(std::vector<point> pu)//最近点对O(nlogn)
{
    int n = pu.size();
    std::sort(pu.begin(), pu.end());
    for (int i = 1; i < n; i++)
        if (pu[i] == pu[i - 1])
            return 0;
    std::set<point, decltype([](cp u, cp v)
    { return u.y == v.y ? u.x < v.x : u.y < v.y; })> s;
    LD ans = (pu[0] - pu[1]).len2();
    for (int i = 0, j = 0; i < n; i++)
    {
        if (ans == 0)
            break;
        auto it = s.begin();
        while (!s.empty() && j < i && sqr(pu[i].x - pu[j].x) >= ans)
            s.erase(pu[j++]);
        auto oit = s.lower_bound(pu[i]);
        it = oit;
        while (ans)
        {
            if (it == s.end())
                break;
            if (sqr(it->y - pu[i].y) >= ans)
                break;
            ans = std::min(ans, (pu[i] - *it).len2());
            it++;
        }
        it = oit;
        while (ans)
        {
            if (it == s.begin())
                break;
            it--;
            if (sqr(it->y - pu[i].y) >= ans)
                break;
            ans = std::min(ans, (pu[i] - *it).len2());
        }
        s.insert(pu[i]);
    }
    return sqrtl(ans);
}

void print(std::vector<point> res)
{
    std::cout << "print:\n";
    int cnt = 0;
    for (auto [x, y]: res)
        std::cout << ++cnt << ' ' << x << ' ' << y << std::endl;
    std::cout << "end\n";
}

int onRight(cl a, cp b)
{ return det(a.t - a.s, b - a.s) <= -eps; }//如果要包含点就-eps，不要就eps
/*
 丢直线 Ax+By+C<0;
if(sgn(b)==0)
            pl.push_back(line(point(-c/a,0),point(-c/a-b,a)));
        else pl.push_back(line(point(0,-c/b),point(-b,-c/b+a)));
 * */

std::vector<point> my_half_plane(std::vector<line> a)
{
    /*要加框取消注释 请注意对于一组解（x,y)x和y是否有要求
    a.push_back({{-INF,-INF},{INF,-INF}});
    a.push_back({{INF,-INF},{INF,INF}});
    a.push_back({{INF,INF},{-INF,INF}});
    a.push_back({{-INF,INF},{-INF,-INF}});
     */
    std::sort(a.begin(), a.end(), [&](auto x, auto y)
    {
        point u = x.t - x.s, v = y.t - y.s;
        if (u.on_up() != v.on_up())return u.on_up() < v.on_up();
        if (sgn(det(u, v)))
            return sgn(det(u, v)) > 0;
        else return sgn(det(x.t - y.s, y.t - y.s)) < 0;
    });
    int n = a.size();
    std::vector<line> que(n + 1);
    std::vector<point> p1(n + 1);
    std::vector<point> p2;
    int left = 0, right = 0;
    que[0] = a[0];
    std::vector<point> sb;
    for (int i = 1; i < n; i++)
    {
        if (sgn(det(a[i].t - a[i].s, a[i - 1].t - a[i - 1].s)) == 0)
            continue;
        while (left < right && onRight(a[i], p1[right]))right--;
        while (left < right && onRight(a[i], p1[left + 1]))left++;
        que[++right] = a[i];
        if (std::abs(det(que[right].t - que[right].s, que[right - 1].t - que[right - 1].s)) <= eps)
        {
            if (onRight(que[right], que[right - 1].s) &&
                dot(que[right].t - que[right].s, que[right - 1].t - que[right - 1].s) <= -eps)
                return sb;
            right--;
            if (!onRight(que[right], a[i].s))
                que[right] = a[i];
        }
        if (left < right)p1[right] = line_intersect(que[right], que[right - 1]);
    }
    while (left < right && onRight(que[left], p1[right]))right--;
    if (right - left <= 1)return sb;
    p1[left] = line_intersect(que[left], que[right]);
    for (int i = left; i <= right; i++)
        p2.push_back(p1[i]);
    return p2;
}
/*
 丢直线 Ax+By+C<0;
if(sgn(b)==0)
            pl.push_back(line(point(-c/a,0),point(-c/a-b,a)));
        else pl.push_back(line(point(0,-c/b),point(-b,-c/b+a)));
 * */
LD get_are(std::vector<point> pu)
{
    LD ans = 0;
    int n = pu.size();
    for (int i = 0; i < n; i++)
        ans += det(pu[i], pu[(i + 1) % n]);
    return ans / 2;
}

LD get_max_inscribed_circle(const std::vector<point> pu)
{
    int n = pu.size();
    std::vector<point> dt(n);
    for (int i = 0; i < n; i++)
        dt[i] = ((pu[(i + 1) % n] - (pu[i] + pu[(i + 1) % n]) / 2).rot90()).unit();
    LD l = 0, r = 1e7;
    std::function<bool(LD)> check = [&](LD r)
    {
        std::vector<line> pl;
        for (int i = 0; i < n; i++)
            pl.push_back({pu[i] + dt[i] * r, pu[(i + 1) % n] + dt[i] * r});
        auto po = my_half_plane(pl);
        return !po.empty();
    };
    while (r - l > 1e-4)
    {
        LD mid = (r + l) / 2;
        if (check(mid))
            l = mid;
        else r = mid;
    }
    return l;
}

long long get_ans(std::vector<point> pu)
{
    long long res = 0;
    LD max_x = -1e18, min_x = 1e18, max_y = -1e18, min_y = 1e18;
    LD len_x, len_y;
    for (int i = 0; i < 3; i++)
        max_x = std::max(max_x, pu[i].x), min_x = std::min(min_x, pu[i].x),
        max_y = std::max(max_y, pu[i].y), min_y = std::min(min_y, pu[i].y);
    len_x = max_x - min_x;
    len_y = max_y - min_y;
    if (len_x < len_y)
    {
        std::sort(pu.begin(), pu.end(), [&](auto u, auto v)
        { return u.x < v.x; });
        long long x_l, x_r;
        if (sgn(pu[0].x - (long long) roundl(pu[0].x)) == 0)
            x_l = (long long) roundl(pu[0].x) + 1;
        else x_l = floorl(pu[0].x) + 1;
        if (sgn(pu[2].x - (long long) roundl(pu[2].x)) == 0)
            x_r = (long long) roundl(pu[2].x) - 1;
        else x_r = floor(pu[2].x);
        for (long long i = x_l; i <= x_r; i++)
        {
            line li = line(point(i, 0), point(i, 1));
            point p1, p2;
            p1 = line_intersect(li, line(pu[0], pu[2]));
            if (i < pu[1].x)
                p2 = line_intersect(li, line(pu[0], pu[1]));
            else
                p2 = line_intersect(li, line(pu[1], pu[2]));
            if (p1.y > p2.y)
                std::swap(p1, p2);
            long long y_l, y_r;
            if (sgn(p1.y - (long long) roundl(p1.y)) == 0)
                y_l = (long long) roundl(p1.y) + 1;
            else y_l = floorl(p1.y) + 1;
            if (sgn(p2.y - (long long) roundl(p2.y)) == 0)
                y_r = (long long) roundl(p2.y) - 1;
            else y_r = floorl(p2.y);
            res += y_r - y_l + 1;
        }
    }
    else
    {
        std::sort(pu.begin(), pu.end(), [&](auto u, auto v)
        { return u.y < v.y; });
        long long y_l, y_r;
        if (sgn(pu[0].y - (long long) roundl(pu[0].y)) == 0)
            y_l = (long long) roundl(pu[0].y) + 1;
        else y_l = floorl(pu[0].y) + 1;
        if (sgn(pu[2].y - (long long) roundl(pu[2].y)) == 0)
            y_r = (long long) roundl(pu[2].y) - 1;
        else y_r = floor(pu[2].y);
        for (long long i = y_l; i <= y_r; i++)
        {
            line li = line(point(0, i), point(1, i));
            point p1, p2;
            p1 = line_intersect(li, line(pu[0], pu[2]));
            if (i < pu[1].y)
                p2 = line_intersect(li, line(pu[0], pu[1]));
            else
                p2 = line_intersect(li, line(pu[1], pu[2]));
            if (p1.x > p2.x)
                std::swap(p1, p2);
            long long x_l, x_r;
            if (sgn(p1.x - (long long) roundl(p1.x)) == 0)
                x_l = (long long) roundl(p1.x) + 1;
            else x_l = floorl(p1.x) + 1;
            if (sgn(p2.x - (long long) roundl(p2.x)) == 0)
                x_r = (long long) roundl(p2.x) - 1;
            else x_r = floorl(p2.x);
            res += x_r - x_l + 1;
        }
    }
    return res;
}
bool check(point a,point b,point c,point d)
{
    point p1=b-a;

    if(p1.x==0||p1.y==0)
    {
        if(sgn(point_to_line(a,line(c,d))-1)==0)
            return true;
    }
    long long res=0;
    long long t=std::gcd((long long)std::abs(p1.y),(long long)std::abs(p1.x));
    res+=t-1;
    p1=d-c;
    t=std::gcd((long long)std::abs(p1.y),(long long)std::abs(p1.x));
    res+=t-1;
    p1=a-d;
    t=std::gcd((long long)std::abs(p1.y),(long long)std::abs(p1.x));
    if(t!=1)
        return false;
    p1=b-c;
    t=std::gcd((long long)std::abs(p1.y),(long long)std::abs(p1.x));
    if(t!=1)
        return false;
    res+=4;
//    res*=2;
    res-=2;
    std::vector<point>pu;
    pu.push_back(a);
    pu.push_back(b);
    pu.push_back(c);
    pu.push_back(d);
    if(sgn(res- get_are(pu)*2)==0)
        return true;
    else return false;


}
void solve()
{
    int n;
    std::cin >> n;
    std::vector<point> pu(n);
    for (int i = 0; i < n; i++)
        pu[i].read();
    long long ans = 0;
    if (n < 4)
    {
        std::cout << "infinitely many" << std::endl;
        return;
    }
    for (int i = 0; i < n; i++)
    {
        point p1 = pu[i], p2 = pu[(i + 1) % n], p3 = pu[(i + 2) % n], p4 = pu[(i + 3) % n];
        if (!ray_intersect_judge(line(p1, p2), line(p4, p3)))
        {
            if(check(p1,p2,p3,p4))
                continue;
            std::cout << "infinitely many" << std::endl;
            return;
        }

        std::vector<point> pu1;
        pu1.push_back(p2);
        pu1.push_back(p3);
        pu1.push_back(line_intersect(line(p1, p2), line(p3, p4)));
        ans += get_ans(pu1);
//        pu[i].print();
//        std::cout<<get_ans(pu1)<<std::endl;
    }
    std::cout << ans << std::endl;
}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0), std::cout.tie(0);
    std::cout << std::fixed << std::setprecision(9);
    int T = 1;
//    std::cin>>T;
    for (int i = 1; i <= T; i++)
        solve();
}