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;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
using ll = long long;
using P = pair<ll, ll>;
const long double PI = acos(-1.0L);
ll GCD(ll a, ll b) { return b?GCD(b, a%b):a; }
ll LCM(ll a, ll b) { return a/GCD(a, b)*b; }

using CP = complex<long double>;

const long double EPS = 1e-10;     // 許容する誤差ε
#define EQ(a, b) (abs((a)-(b)) < EPS)   // 2つのスカラーが等しいかどうか
#define EQV(a, b) (EQ((a).real(), (b).real()) && EQ((a).imag(), (b).imag()))    // 2つのベクトルが等しいかどうか

// double length = abs(a);     // ベクトルaの絶対値
// double distance = abs(a-b);     // 2点a,b間の距離
// CP b = a/abs(a);    // ベクトルaの単位ベクトル
// CP n1 = a*CP(0,+1); CP n2 = a*CP(0,-1);  // ベクトルaの法線ベクトル
// CP un1 = (a*CP(0,+1)/abs(a)); CP un2 = (a*CP(0,-1)/abs(a));  // ベクトルaの単位法線ベクトル

// 内積(dot product) : a・b = |a||b|cosΘ
long double dot(CP a, CP b) {
    return (a.real()*b.real() + a.imag()*b.imag());
}

// 外積(cross product) : a×b = |a||b|sinΘ
long double cross(CP a, CP b) {
    return (a.real()*b.imag() - a.imag()*b.real());
}

// 2直線の直交判定 : a⊥b ⇔ dot(a,b) = 0
int is_orthogonal(CP a1, CP a2, CP b1, CP b2) {
    return EQ(dot(a1-a2, b1-b2), 0.0);
}

// 2直線の平行判定 : a//b ⇔ cross(a,b) = 0
int is_parallel(CP a1, CP a2, CP b1, CP b2) {
    return EQ(cross(a1-a2, b1-b2), 0.0);
}

// 点cが直線a,b上にあるかないか
int is_point_on_line(CP a, CP b, CP c) {
    return EQ(cross(b-a, c-a), 0.0);
}

// 点cが線分a,b上にあるかないか
int is_point_on_lines(CP a, CP b, CP c) {
    // |a-c|+|c-b| <= |a-b|なら線分上
    return (abs(a-c)+abs(c-b) < abs(a-b)+EPS);
}

// a1,a2を端点とする線分とb1,b2を端点とする線分の交差判定
int is_intersected_lines(CP a1, CP a2, CP b1, CP b2) {
    if(is_parallel(a1, a2, b1, b2)) {
        // 平行なので線分の重なり判定
        return is_point_on_lines(a1, a2, b1) || is_point_on_lines(a1, a2, b2) ||
               is_point_on_lines(b1, b2, a1) || is_point_on_lines(b1, b2, a2);
    }
    return (cross(a2-a1, b1-a1)*cross(a2-a1, b2-a1) < EPS) &&
           (cross(b2-b1, a1-b1)*cross(b2-b1, a2-b1) < EPS);
}

// a1,a2を端点とする線分とb1,b2を端点とする線分の交点計算
CP intersection_lines(CP a1, CP a2, CP b1, CP b2) {
    CP b = b2-b1;
    long double d1 = abs(cross(b, a1-b1));
    long double d2 = abs(cross(b, a2-b1));
    long double t = d1/(d1+d2);
    return a1+(a2-a1)*t;
}

// a1,a2を通る直線とb1,b2を通る直線の交差判定
int is_intersected_line(CP a1, CP a2, CP b1, CP b2) {
    return !EQ(cross(a1-a2, b1-b2), 0.0);
}

// a1,a2を通る直線とb1,b2を通る直線の交点計算(平行ではない前提)
CP intersection_line(CP a1, CP a2, CP b1, CP b2) {
    CP a = a2-a1; CP b = b2-b1;
    return a1 + a*cross(b, b1-a1)/cross(b, a);
}

// 点a,bを通る直線と点cとの距離
long double distance_line_p(CP a, CP b, CP c) {
    return abs(cross(b-a, c-a))/abs(b-a);
}

// 点a,bを端点とする線分と点cとの距離
long double distance_lines_p(CP a, CP b, CP c) {
    if(dot(b-a, c-a) < EPS) return abs(c-a);
    if(dot(a-b, c-b) < EPS) return abs(c-b);
    return abs(cross(b-a, c-a))/abs(b-a);
}

// 点a1,a2を端点とする線分と点b1,b2を端点とする線分の最短距離
long double distance_lines_lines(CP a1, CP a2, CP b1, CP b2) {
    long double res = 1e18;
    if(is_intersected_lines(a1, a2, b1, b2)) return 0.0L;
    res = min(res, distance_lines_p(a1, a2, b1));
    res = min(res, distance_lines_p(a1, a2, b2));
    res = min(res, distance_lines_p(b1, b2, a1));
    res = min(res, distance_lines_p(b1, b2, a2));
    return res;
}

// s,tを通る直線に対する点pの射影
CP projection(CP s, CP t, CP p) {
    if(EQV(s, t)) return s;
    CP base = t-s;
    return s + base*(dot(p-s, base)/norm(base));
}

// s,tを通る直線に対する点pの反射
CP reflection(CP s, CP t, CP p) {
    CP tmp = projection(s, t, p) - p;
    return p + tmp*2.0L;
}

// n多角形の面積計算
long double polygon_area(const vector<CP> &v) {
    int n = v.size();
    long double res = 0;
    for(int i = 0; i < n; ++i) {
        res += cross(v[(i+n-1)%n], v[(i+n)%n]);
    }
    return fabsl(res)/2.0L;
}

// n多角形の凸性判定
int is_convex(const vector<CP> &v) {
    int n = v.size();
    for(int i = 0; i < n; ++i) {
        if(cross(v[(i+1)%n]-v[i], v[(i+2)%n]-v[(i+1)%n]) < -EPS) return 0;
    }
    return 1;
}

// 凸包
vector<CP> convex_hull(vector<CP> &v) {
    // x座標→y座標で頂点をソート
    auto lmd = [&](const CP &l, const CP &r) {
        if(l.imag() != r.imag()) return l.imag() < r.imag();
        return l.real() < r.real();
        return l.imag() < r.imag();
    };
    vector<CP> res;     // 凸包を構成する頂点
    int n = v.size();
    sort(v.begin(), v.end(), lmd);
    int k = 0;
    res.resize(n*2);
    // 下側凸包
    for(int i = 0; i < n; ++i) {
        while(k > 1 && cross(res[k-1]-res[k-2], v[i]-res[k-1]) < 0) {
            --k;
        }
        res[k++] = v[i];
    }
    // 上側凸包
    for(int i = n-2, t = k; i >= 0; --i) {
        while(k > t && cross(res[k-1]-res[k-2], v[i]-res[k-1]) < 0) {
            --k;
        }
        res[k++] = v[i];
    }
    res.resize(k-1);
    return res;
}

// 凸多角形の直径
long double convex_diameter(vector<CP> &v) {
    vector<CP> cv = convex_hull(v);
    int n = cv.size();
    if(n == 2) return abs(cv[0]-cv[1]);     // 凸包が潰れている例外処理
    int i = 0, j = 0;   // x軸方向に最も遠い点対
    for(int k = 0; k < n; ++k) {
        if(cv[k].real() < cv[i].real()) i = k;
        if(cv[k].real() > cv[j].real()) j = k;
    }
    long double res = 0;
    int si = i, sj = j;
    while(i != sj || j != si) {     // 180度回転で終了
        res = max(res, abs(cv[i]-cv[j]));
        if(cross(cv[(i+1)%n]-cv[i], cv[(j+1)%n]-cv[j]) < 0) {
            (++i) %= n;
        }else {
            (++j) %= n;
        }
    }
    return res;
}

// 凸多角形を点s,tを通る直線で切断
vector<CP> convex_cut(const vector<CP> &v, const CP &s, const CP &t) {
    vector<CP> res;
    int n = v.size();
    for(int i = 0; i < n; ++i) {
        CP nows = v[i], nowt = v[(i+1)%n];
        if(cross(t-s, nows-s) >= -EPS) res.emplace_back(nows);
        if(cross(t-s, nows-s)*cross(t-s, nowt-s) < 0) {
            res.emplace_back(intersection_line(s, t, nows, nowt));
        }
    }
    return res;
}

// n多角形に対する点pの包含関係(自己交差多角形は例外)
int contain_polygon_point(const vector<CP> &v, CP p) {
    int contain = 0, on_segment = 0;
    int n = v.size();
    for(int i = 0; i < n; ++i) {
        on_segment |= is_point_on_lines(v[i], v[(i+1)%n], p);   // 辺上判定
        CP s = v[i]-p, t = v[(i+1)%n]-p;
        if(s.imag() > t.imag()) swap(s, t);     // 下側を基準にする
        if(s.imag()*t.imag() <= 0 && t.imag() > 0 && cross(s, t) > 0) {
            contain = !contain;     // 交差回数が奇数なら内側
        }
    }
    if(on_segment) return 1;    // 辺上
    if(contain) return 2;       // 内側
    return 0;       // 外側
}

// 3点の位置関係を判定
int calc_clockwise(CP p0, CP p1, CP p2) {
    CP x = p1-p0, y = p2-p0;
    if(cross(x, y) > EPS) return 1;     // "COUNTER_CLOCKWISE"
    if(cross(x, y) < -EPS) return -1;   // "CLOCKWISE"
    if(dot(x, y) < 0) return 2;         // "ONLINE_BACK"
    if(norm(x) < norm(y)) return -2;    // "ONLINE_FRONT"
    return 0;                           // "ON_SEGMENT" 
}

int main() {
    int n; cin >> n;
    vector<CP> point;
    for(int i = 0; i < n; ++i) {
        long double a, b; cin >> a >> b;
        point.emplace_back(CP(a, b));
    }
    int q; cin >> q;
    for(int i = 0; i < q; ++i) {
        long double x, y, z, w;
        cin >> x >> y >> z >> w;
        CP p1(x, y), p2(z, w);
        cout << fixed << setprecision(10);
        cout << polygon_area(convex_cut(point, p1, p2)) << endl;
    }
}