Problem: <image>


As shown in the figure above, cut a convex polygon g by a line p1p2 and print the area of the cut polygon which is on the left-hand side of the line.

g is represented by a sequence of points p1, p2,..., pn where line segments connecting pi and pi+1 (1 ≤ i ≤ n−1) are sides of the convex polygon. The line segment connecting pn and p1 is also a side of the polygon.

Constraints

* 3 ≤ n ≤ 100
* 1 ≤ q ≤ 100
* -10000 ≤ xi, yi ≤ 10000
* -10000 ≤ p1x,p1y,p2x,p2y ≤ 10000
* No point in g will occur more than once.
* p1 ≠ p2

Input

The input is given in the following format:


g (the sequence of the points of the polygon)
q (the number of queries = the number of target lines)
1st query
2nd query
:
qth query


g is given as a sequence of points p1,..., pn in the following format:


n
x1 y1
x2 y2
:
xn yn


The first integer n is the number of points. The coordinate of the i-th point pi is given by two integers xi and yi. The coordinates of points are given in the order of counter-clockwise visit of them. Note that all interior angles of given convex polygons are less than or equal to 180.

For each query, a line represented by two points p1 and p2 is given. The coordinates of the points are given by four integers p1x, p1y, p2x and p2y.

Output

For each query, print the area of the cut polygon. The output values should be in a decimal fraction with an error less than 0.00001.

Example

Input

4
1 1
4 1
4 3
1 3
2
2 0 2 4
2 4 2 0


Output

2.00000000
4.00000000

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
#define ln '\n'

//////////////////////////////////////////////////////////////////////////////

using DD = double; // 精度が足りないときはlong double
#define EPS (1e-10)
#define equals(a, b) (fabs((a) - (b)) < EPS)

//点
struct Point {
    DD x, y;
    Point (DD x = 0, DD y = 0): x(x), y(y) {}

    Point& operator+=(const Point &p) { x += p.x; y += p.y; return *this;}
    Point operator+(const Point &p) const { return Point(*this) += p;}
    Point& operator-=(const Point &p) { x -= p.x; y -= p.y; return *this;}
    Point operator-(const Point &p) const { return Point(*this) -= p;}
    Point& operator*=(DD a) { x *= a; y *= a; return *this;}
    Point operator*(DD a) const { return Point(*this) *= a;}
    Point& operator/=(DD a) { x /= a; y /= a; return *this;}
    Point operator/(DD a) const { return Point(*this) /= a;}
    bool operator== (const Point &p) const { return fabs(x - p.x) < EPS && fabs(y - p.y) < EPS;}
    bool operator< (const Point &p) const {
        if (equals(x, p.x)) return y < p.y;
        return x < p.x;
    }
    friend istream& operator >>(istream& is, Point& p) { is >> p.x >> p.y; return is;}
    friend ostream& operator <<(ostream& os, const Point& p) { os << p.x << " " << p.y; return os;}
};

//ベクトル
typedef Point Vector;

inline DD norm(const Vector &a) { return a.x * a.x + a.y * a.y;}
inline DD abs(const Vector &a) { return sqrt(norm(a));}
inline DD dot(const Vector &a, const Vector &b) { return a.x * b.x + a.y * b.y;}
inline DD cross(const Vector &a, const Vector &b) { return a.x * b.y - a.y * b.x;}
inline Point rot(const Point &p, DD ang) { return Point(cos(ang) * p.x - sin(ang) * p.y, sin(ang) * p.x + cos(ang) * p.y);}
inline Point rot90(const Point &p) { return Point(-p.y, p.x);}

//線分
struct Segment {
    Point p1,p2;
    Segment() = default;
    Segment(Point p1, Point p2) : p1(p1),p2(p2) {}
};

//直線
typedef Segment Line;

// 円
struct Circle {
    Point c;
    DD r;
    Circle(Point c = Point(), DD r = 0): c(c), r(r) {}
};

//多角形
typedef vector<Point> Polygon;

//射影
Point project(const Segment &s, const Point &p) {
    Vector base = s.p2 - s.p1;
    DD r = dot(p - s.p1, base) / norm(base);
    return s.p1 + base * r;
}

//線対称
inline Point reflect(const Segment &s, const Point &p) {return p + (project(s,p) - p) * 2;}

int ccw(const Point &p0, const Point &p1, const Point &p2) {
    Vector a = p1 - p0;
    Vector b = p2 - p0;
    if (cross(a,b) > EPS) return 1; //p0,p1から見てp2は左側(反時計回り)
    if (cross(a,b) < -EPS) return -1; //p0,p1から見てp2は右側(時計回り)
    if (dot(a,b) < -EPS) return 2; //p2-p0-p1の順に一直線上
    if (norm(a) < norm(b)) return -2; //p0-p1-p2の順に一直線上
    return 0; //p0-p2-p1の順に一直線上
}

//線分p1,p2とp3,p4の交差判定
inline bool intersect(const Point &p1, const Point &p2, const Point &p3, const Point &p4) { return (ccw(p1, p2, p3) * ccw(p1, p2, p4) <= 0 && ccw(p3, p4, p1) * ccw(p3, p4, p2) <= 0);}
inline bool intersect(const Segment &s1, const Segment &s2) { return intersect(s1.p1, s1.p2, s2.p1, s2.p2);}

inline DD getDistanceLP(const Line &l, const Point &p) { return abs(cross(l.p2 - l.p1,p - l.p1) / abs(l.p2 - l.p1));}
DD getDistanceSP(const Segment &s, const Point &p) {
    if (dot(s.p2 - s.p1,p - s.p1) < 0.0) return abs(p - s.p1);
    if (dot(s.p1 - s.p2,p - s.p2) < 0.0) return abs(p - s.p2);
    return getDistanceLP(s, p);
}
DD getDistance(const Segment &s1, const Segment &s2) {
    if (intersect(s1, s2)) return (DD)0;
    return min({getDistanceSP(s1, s2.p1), getDistanceSP(s1, s2.p2), getDistanceSP(s2, s1.p1), getDistanceSP(s2, s1.p2)});
}

//線分と線分の交点
Point getCrossPoint(const Segment &s1, const Segment &s2) {
    Vector base = s2.p2 - s2.p1;
    DD d1 = abs(cross(base, s1.p1 - s2.p1));
    DD d2 = abs(cross(base, s1.p2 - s2.p1));
    DD t = d1 / (d1 + d2);
    return s1.p1 + (s1.p2 - s1.p1) * t;
}

//円と直線の交差判定
inline bool intersect(const Circle &c, const Line &l) { return getDistanceLP(l, c.c) - c.r < EPS;}
//円と円の交差判定
inline bool intersect(const Circle &c1, const Circle &c2) { return abs(c1.c - c2.c) - (c1.r + c2.r) < EPS && fabs(c1.r - c2.r) - abs(c1.c - c2.c) < EPS;}

//円と線分の交点
pair<Point, Point> getCrossPoints(const Circle &c, const Line &l) {
    assert(intersect(c,l));
    Vector pr = project(l, c.c);
    Vector e = (l.p2 - l.p1) / abs(l.p2 - l.p1);
    DD base = sqrt(c.r * c.r - norm(pr - c.c));
    return make_pair(pr + e * base, pr - e * base);
}

inline DD arg(const Vector &p) { return atan2(p.y, p.x);}
inline Vector polar(DD a, DD r) { return Point(cos(r) * a, sin(r) * a);}

//円と円の交点
pair<Point, Point> getCrossPoints(const Circle &c1, const Circle &c2) {
    assert(intersect(c1, c2));
    DD d = abs(c1.c - c2.c);
    DD a = acos((c1.r * c1.r + d * d - c2.r * c2.r) / (DD(2) * c1.r * d));
    DD t = arg(c2.c - c1.c);
    return make_pair(c1.c + polar(c1.r, t + a), c1.c + polar(c1.r, t - a));
}

//多角形の面積
DD area(const Polygon &g) {
    const int N = g.size();
    DD ret = 0;
    for (int i = 0; i < N; ++i) {
        ret += cross(g[i],g[(i+1)%N]);
    }
    return fabs(ret)/2;
}

// 多角形-点の包含判定
int containment(const Polygon &g, const Point &p) {
    const int N = g.size();
    int cnt = 0;
    for (int i = 0; i < N; ++i) {
        if (norm(g[i] - p) < EPS || norm(g[(i+1)%N] - p) < EPS || ccw(g[i], g[(i+1)%N], p) == 0) {
            return 1; // pがgの辺上に存在する
        }
        Point I = Point(2e9 + p.x, 2e9 + 574677631 + p.y);
        if (ccw(I, p, g[i]) == 0 || ccw(I, p, g[(i+1)%N]) == 0) continue;
        if (intersect(I, p, g[i], g[(i+1)%N])) ++cnt;
    }
    if (cnt&1) return 2; // pがgに含まれる
    else return 0; // pがgに含まれない
}

//象限
int ort(const Point &a) {
    if (norm(a) < EPS) return 0;
    if (a.y > 0) return a.x > 0 ? 1 : 2;
    return a.x > 0 ? 4 : 3;
}

bool xsort(const Point &a, const Point &b) {
    if (equals(a.x, b.x)) return a.y < b.y;
    return a.x < b.x;
}

bool ysort(const Point &a, const Point &b) {
    if (equals(a.y, b.y)) return a.x < b.x;
    return a.y < b.y;
}

bool argsortcross(const Point &a, const Point &b) {
    int ao = ort(a), bo = ort(b);
    if (ao != bo) return ao < bo;
    return cross(a,b) > 0;
}

bool argsortatan2(const Point &a, const Point &b) {
    return atan2(a.y, a.x) < atan2(b.y, b.x);
}

//凸包
Polygon andrewScan(Polygon s) {
    Polygon u,l;
    const int N = s.size();
    if (N < 3) return s;
    sort(s.begin(), s.end(), xsort);
    u.emplace_back(s[0]);
    u.emplace_back(s[1]);
    l.emplace_back(s[N-1]);
    l.emplace_back(s[N-2]);
    
    for (int i = 2; i < s.size(); ++i) {
        // 凸包上の点も含めるなら ccw() == 1
        for (int n = u.size(); n >= 2 && ccw(u[n-2],u[n-1],s[i]) != -1; --n) {
            u.pop_back();
        }
        u.emplace_back(s[i]);
    }

    for (int i = N - 3; i >= 0; --i) {
        // 凸包上の点も含めるなら ccw() == 1
        for (int n = l.size(); n >= 2 && ccw(l[n-2], l[n-1], s[i]) != -1; --n) {
            l.pop_back();
        }
        l.emplace_back(s[i]);
    }

    reverse(l.begin(), l.end());
    for (int i = u.size() - 2; i >= 1; --i) l.emplace_back(u[i]);

    return l;
}

//最遠点対
DD farthestpointpair(const Polygon &g) {
    const int N = g.size();
    if (N == 2) return abs(g[1] - g[0]);
    int i = 0, j = 0;
    for (int k = 0; k < N; ++k) {
        if (g[k].y > g[i].y) i = k;
        if (g[k].y < g[j].y) j = k;
    }

    DD ret = 0;
    int si = i, sj = j;
    while (i != sj || j != si) {
        ret = max(ret, abs(g[i]-g[j]));
        if (cross(g[(i+1)%N] - g[i], g[(j+1)%N] - g[j]) < -EPS) {
            i = (i+1)%N;
        } else {
            j = (j+1)%N;
        }
    }

    return ret;
}

/////////////////////////////////////////////////////////////////////////////////////////////

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int N; cin >> N;
    Polygon P(N);
    for (int i = 0; i < N; ++i) cin >> P[i];

    int Q; cin >> Q;
    while (Q--) {
        Point p1,p2; cin >> p1 >> p2;
        Polygon ans;
        for (int i = 0; i < N; ++i) {
            if (ccw(p1, p2, P[i]) != -1) {
                ans.emplace_back(P[i]);
            }
            if (ccw(p1,p2,P[i])*ccw(p1,p2,P[(i+1)%N]) <= 0) {
                if (fabs(cross(p1-p2,P[i]-P[(i+1)%N])) < EPS) continue;
                ans.emplace_back(getCrossPoint(Segment(P[i],P[(i+1)%N]),Segment(p1,p2)));
            }
        }

        cout << fixed << setprecision(12) << area(ans) << ln;
    }
}