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:
//
// ?¨???????????????????????????? double ?????§?????£????????????
// ?????????int?????§?¨??????§????????????double?????§????????????????????????
//
#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <functional>

using namespace std;

#define fst first
#define snd second
#define all(c) ((c).begin()), ((c).end())
#define TEST(x,a) { auto y=(x); if (y!=a) { cout << "line " << __LINE__  << #x << " = " << y << " != " << a << endl; exit(-1); } }


// implementation note: use EPS only this function
// usage note: check sign(x) < 0, sign(x) > 0, or sign(x) == 0
const double EPS = 1e-8;
int sign(double x) {
  const double EPS = 1e-8;
  if (x < -EPS) return -1;
  if (x > +EPS) return +1;
  return 0;
}
struct point {
  typedef double T;
  T x, y; 
  point &operator+=(point p) { x += p.x; y += p.y; return *this; }
  point &operator-=(point p) { x -= p.x; y -= p.y; return *this; }
  point &operator*=(T a)     { x *= a;   y *= a;   return *this; }
  point &operator/=(T a)     { return *this *= (1.0/a); }
  point operator-() const    { return {-x, -y}; }
  friend point operator+(point p, point q) { return p += q; }
  friend point operator-(point p, point q)    { return p -= q; }
  friend point operator*(T a, point p) { return p *= a; }
  friend point operator*(point p, T a) { return p *= a; }
  friend point operator/(point p, T a) { return p /= a; }
  bool operator==(point p) const { return !sign(x-p.x) && !sign(y-p.y); }
  bool operator<(point p) const { return x!=p.x ? x<p.x : y<p.y; } // for sort

  friend T dot(point p, point q) { return p.x*q.x+p.y*q.y; }
  friend T cross(point p, point q) { return p.x*q.y-p.y*q.x; } // cross(ex, ey) = 1
  friend point ortho(point p) { return {-p.y, p.x}; }

  friend istream &operator>>(istream &is, point &p) { is>>p.x>>p.y;return is; }
  friend ostream &operator<<(ostream &os, point &p) { os<<"("<<p.x<<","<<p.y<<")"; return os; }
};

struct line    { point p, q; };
bool operator==(line L, line M) {
  return !sign(cross(L.p-L.q,M.p-M.q)) &&
         !sign(cross(L.p-L.q,M.p-L.p));
}

struct segment { point p, q; };
struct circle  { point p; point::T r; };

vector<point> intersect(line L, point p) {
  if (sign(cross(L.p-p, L.q-p)) != 0) return {};
  return {p};
}
vector<point> intersect(point p, line L) {
  return intersect(L, p);
}

vector<point> intersect(segment S, point p) {
  if (sign(cross(S.p-p, S.q-p)) != 0) return {};
  if (sign(  dot(S.p-p, S.q-p))  > 0) return {};
  return {p};
}
vector<point> intersect(point p, segment S) { 
  return intersect(S, p);
}

//
// Crosspoint equation is
//   L.p + (L.q - L.p) t == M.p + (M.q - M.p) s
// Taking a cross product with (M.q - M.p), we have
//   (M.q - M.p) x (L.q - L.p) t == (M.q - M.p) x (M.p - L.p) 
//   ~~~~~~~~~~~~a~~~~~~~~~~~~      ~~~~~~~~~~~~b~~~~~~~~~~~~
//
// If a != 0, these two lines have a proper crosspoint.
// If a == 0 and b == 0, these two lines are the same line
// thus any t gives a solution.
// Otherwise, these two lines are parallel.
//
vector<point> intersect(line L, line M) {
  auto a = cross(M.q - M.p, L.q - L.p);
  auto b = cross(L.p - M.p, L.q - L.p); 
  if (sign(a) != 0) return {M.p + b/a*(M.q - M.p)}; // properly crossing
  if (sign(b) == 0) return {M.p, M.q};              // same line
  return {};                                        // disjoint parallel
}

vector<point> intersect(line L, segment S) {
  auto a = cross(S.q - S.p, L.q - L.p);
  auto b = cross(L.p - S.p, L.q - L.p); 
  if (a < 0) { a *= -1; b *= -1; }
  if (sign(b) < 0 || sign(a-b) < 0) return {};      // no intersect
  if (sign(a) != 0) return {S.p + b/a*(S.q - S.p)}; // properly crossing
  if (sign(b) == 0) return {S.p, S.q};              // same line
  return {};                                        // disjoint parallel
}

// intersection of two segments
vector<point> intersect(segment S, segment T) {
  auto a = cross(S.q - S.p, T.q - T.p);
  auto b = cross(T.p - S.p, T.q - T.p); 
  auto c = cross(S.q - S.p, S.p - T.p);
  if (a < 0) { a = -a; b = -b; c = -c; }
  if (sign(b) < 0 || sign(a-b) < 0 ||
      sign(c) < 0 || sign(a-c) < 0) return {};      // disjoint
  if (sign(a) != 0) return {S.p + b/a*(S.q - S.p)}; // properly crossing
  vector<point> ps;                                 // same line
  auto insert_if_possible = [&](point p) {
    for (auto q: ps) if (sign(dot(p-q, p-q)) == 0) return;
    ps.push_back(p);
  };
  if (sign(dot(S.p-T.p, S.q-T.p)) <= 0) insert_if_possible(T.p);
  if (sign(dot(S.p-T.q, S.q-T.q)) <= 0) insert_if_possible(T.q);
  if (sign(dot(T.p-S.p, T.q-S.p)) <= 0) insert_if_possible(S.p);
  if (sign(dot(T.p-S.q, T.q-S.q)) <= 0) insert_if_possible(S.q);
  return ps;
}

// closest point on L
point projection(point p, line L) {
  auto a = dot(L.p-L.q, L.p-L.q);
  auto b = dot(L.p-p,   L.p-L.q);
  return L.p + a/b*(L.q - L.p);
}

// closest point on S
point projection(point p, segment S) {
  auto a = dot(S.p-S.q, S.p-S.q);
  auto b = dot(S.p - p, S.p-S.q);
  if (sign(b) < 0)   return S.p;
  if (sign(a-b) < 0) return S.q;
  return S.p + b/a*(S.q - S.p);
}

// reflected point with L
point reflection(point p, line L) {
  auto a = dot(L.p-L.q, L.p-L.q);
  auto b = dot(L.p-p,   L.p-L.q);
  return 2 * (L.p + a/b*(L.q - L.p)) - p;
}

// intersection points of two circles
vector<point> intersect(circle C, circle D) {
  if (C.r < D.r) swap(C, D); 
  auto pow2 = [](point::T a) { return a*a; };
  auto d2 = dot(C.p-D.p, C.p-D.p);
  if (sign(d2) == 0) {
    if (sign(C.r-D.r) != 0) return {};
    return {{C.p.x+C.r, C.p.y}, {C.p.x, C.p.y+C.r}, {C.p.x-C.r, C.p.y}};
  }
  int outer = sign(d2 - pow2(C.r + D.r));
  int inner = sign(d2 - pow2(C.r - D.r));
  if (outer > 0 || inner < 0) return {};
  if (outer == 0) return {(C.r*D.p+D.r*C.p)/(C.r+D.r)};
  if (inner == 0) return {(C.r*D.p-D.r*C.p)/(C.r-D.r)};
  auto eta = (pow2(C.r) - pow2(D.r) + d2)/(2.0 * d2);
  auto mu = sqrt(pow2(C.r)/d2 - pow2(eta));
  point q = C.p + eta*(D.p-C.p), v = ortho(mu*(D.p - C.p));
  return {q + v, q - v};
}

vector<point> intersect(line L, circle C) {
  point u = L.q - L.p, v = L.p - C.p;
  auto a = dot(u,u), b = dot(u,v), c = dot(v,v) - C.r*C.r;
  if (b < 0) { a = -a; b = -b; c = -c; }
  auto det = b*b - a*c;
  if (sign(det) <  0) return {};              // no solution
  if (sign(det) == 0) return {L.p - b/a*u};   // touch inner/outer
  return {L.p - (b + sqrt(det))/a*u,          // properly intersect
          L.p - c/(b + sqrt(det))*u};
}
vector<point> intersect(circle C, line L) {
  return intersect(L, C);
}
bool incircle(circle C, point p) {
  return dot(C.p-p,C.p-p) <= C.r*C.r;
}

point::T dist(point p, point q) {
  return sqrt(dot(p - q, p - q));
}
point::T dist(point p, line L) {
  return dist(p, projection(p, L));
}
point::T dist(line L, point p) {
  return dist(p, L);
}
point::T dist(line L, line M) {
  if (sign(cross(L.p-L.q,M.p-M.q))) return 0; // cross
  return dist(L.p, M);
}
point::T dist(point p, segment S) {
  return dist(p, projection(p, S));
}
point::T dist(line L, segment S) {
  if (intersect(L, S).size()) return 0;
  return min(dist(L, S.p), dist(L, S.q));
}
point::T dist(segment S, line L) {
  return dist(L, S); 
}
point::T dist(segment S, segment T) {
  if (intersect(S, T).size()) return 0;
  return min({dist(S.p,T), dist(S.q,T), dist(T.p,S), dist(T.q,S)});
}

/*
vector<line> tangent(circle C, circle D) {
point::T d = abs(D.p - C.p);
  if (sign(d) == 0) return {}; // same origin
  point v = (D.p - C.p) / d;
  vector<line> ls;
  for (int s = -1; s <= 1; s += 2) {
  point::T c = abs(C.r - s*D.r) / d;
    if (sign(1 - c*c) == 0) {        // touch inner/outer
      point n = point(1,1);
      ls.push_back(line(C.p+C.r*v*n, C.p+C.r*v*conj(n)));
    } else if (sign(1 - c*c) > 0) {  // properly intersect
      point n = point(c, sqrt(1-c*c));
      ls.push_back(line(C.p-s*C.r*v*n,       D.p-D.r*v*n));
      ls.push_back(line(C.p-s*C.r*v*conj(n), D.p-D.r*v*conj(n)));
    }
  }
  return ls;
}
*/
//????§???¢??¨??????????????????
int contains(vector<point> ps, point p) {
  bool in = false;
  for (int i = 0; i < ps.size(); ++i) {
    point a = ps[i] - p, b = ps[i+1==ps.size()?0:i+1] - p;
    if (a.y > b.y) swap(a, b);
    if (a.y <= 0 && 0 < b.y)
      if (cross(a, b) < 0) in = !in;
    if (sign(cross(a, b)) == 0 && sign(dot(a, b)) <= 0) 
      return true; // point on edge
  }
  return in;
}

int ccw(point a, point b, point c) {
  b = b - a; c = c - a;
  if(cross(b, c) > 0)     return +1; // counter clockwise
  if(cross(b, c) < 0)     return -1; // clockwise
  if(dot(b, c) < 0)       return +2; // c--a--b on line
  if(dot(b,b) < dot(c,c)) return -2; // a--b--c on line
  return 0;
}
//
// is a convex hull with the smallest number of points.
//
vector<point> convex_hull(vector<point> ps) {
  int n = ps.size(), k = 0;
  sort(all(ps));
  vector<point> ch(2*n);
  auto cond = [&](point p, point q, point o) {
    int a = sign(cross(p-o, q-o)), b = sign(dot(p-o, q-o));
    return a < 0 || (a == 0 && b >= 0); // contains points on the edges
    // return sign(a) < 0; // does not contain points on the edges
  };
  for (int i = 0; i < n; ch[k++] = ps[i++]) // lower-hull
    while (k > 2 && cond(ch[k-2], ch[k-1], ps[i])) ++k;
  for (int i = n-2, t = k; i >= 0; ch[k++] = ps[i--]) // upper-hull
    while (k > t && cond(ch[k-2], ch[k-1], ps[i])) ++k;
  ch.resize(k-1);
  return ch;
}

point::T area(vector<point> ps) {
  if (ps.size() <= 2) return 0;
  auto a = cross(ps.back(), ps[0]);
  for (int i = 0; i+1 < ps.size(); ++i) 
    a += cross(ps[i], ps[i+1]);
  return a/2;
}

vector<point> convex_cut2(vector<point> ps, line L) {
  vector<point> qs;
  for (int i = 0; i < ps.size(); ++i) {
    int j = (i == ps.size()-1 ? 0 : i+1);
    if (sign(cross(L.p - ps[i], L.q - ps[i])) >= 0) qs.push_back(ps[i]); 
    if (sign(cross(L.p - ps[i], L.q - ps[i])) *
        sign(cross(L.p - ps[j], L.q - ps[j])) < 0) {
      auto a = cross(ps[j] - ps[i], L.q - L.p);
      auto b = cross(L.p - ps[i], L.q - L.p); 
      qs.push_back(ps[i] + b/a*(ps[j] - ps[i]));
    }
  }
  return qs;
}
point crosspoint(line l, line m) {
  double A = cross(l.q - l.p, m.q - m.p);
  double B = cross(l.q - l.p, l.q - m.p);
  if (abs(A) < EPS && abs(B) < EPS) return m.p; // same line
  return m.p + B / A * (m.q - m.p);
}
typedef vector<point> polygon;
polygon convex_cut(polygon P, line l) {
  polygon Q;
  for (int i = 0; i < P.size(); ++i) {
    point A = P[i], B = P[i+1==P.size()?0:i+1];
    if (ccw(l.p, l.q, A) != -1) Q.push_back(A);
    if (ccw(l.p, l.q, A)*ccw(l.p, l.q, B) < 0)
      Q.push_back(crosspoint(line({A, B}), l));
  }
  return Q;
}



circle three_point_circle(point p, point q, point r) {
  point u = q - p, v = r - p; u = {-u.y, u.x};
  point o = (p+q + u*dot(r-q,v)/dot(u,v))/2;
  return {o, sqrt(dot(p - o, p - o))};
}

double quadraliteral_area(double a, double b, double c, double d) {
  double s = a+b+c+d;
  return sqrt((s-a)*(s-b)*(s-c)*(s-d))/4;
}
double triangle_area(double a, double b, double c) {
  return quadraliteral_area(a, b, c, 0);
}
double excircle_radius(double a, double b, double c) {
  return a*b*c/4/triangle_area(a, b, c);
}
double incircle_radius(double a, double b, double c) {
  return 2*triangle_area(a,b,c)/(a+b+c);
}



void angular_sort(vector<point> &ps) {
  point o = {0, 0};
  auto comp = [&](point p, point q) {
    p = p - o; q = q - o;
    if (sign(p.y) != sign(q.y)) return p.y > q.y; 
    if (!sign(p.y) && !sign(q.y)) { 
      if (sign(p.x) >= 0 || sign(q.x) >= 0) return p.y > q.y; 
      else                                  return p.x < q.x;
    }
    if (sign(cross(p, q))) return cross(p, q) < 0;
    return dot(p, p) > dot(q, q);
  };
  sort(all(ps));
}


/*
int maximum_points_on_a_line(vector<point> ps) {
  sort(all(ps)); // assume dx >= 0; if dx == 0 then dy >= 0
  int max_count = 0;
  for (int i = 0; i < ps.size(); ) {
    int k = 1;
    while (sign(norm(ps[i] - ps[i+k])) == 0) ++k;

    vector<point> slope;
    for (int j = i+1; j < ps.size(); ++j) 
      slope.push_back(ps[j] - ps[i]);
    auto comp = [&](point p, point q) { return p.y * q.x < q.y * p.x; };
    sort(all(slope), comp);
    for (int i = 0, k; i < slope.size(); i += k) {
      for (k = 1; slope[i] == slope[i+k]; ++k);
      max_count = max(max_count, base + k);
    }
  }
  return max_count;
}
*/


void triangulate(vector<point> ps) {
  int n = ps.size();
  vector<int> next(n);
  for (int i = 0; i < n-1; ++i) next[i] = i+1;
  auto is_ear = [&](int i, int j, int k) {
    if (sign(cross(ps[j]-ps[i], ps[k]-ps[i])) <= 0) return false;
    for (int l = 0; l < n; ++l) {
      if (l == i || l == j || l == k) continue;
      if (sign(cross(ps[i]-ps[l], ps[j]-ps[l])) >= 0
       && sign(cross(ps[j]-ps[l], ps[k]-ps[l])) >= 0
       && sign(cross(ps[k]-ps[l], ps[i]-ps[l])) >= 0) return false;
    }
    return true;
  };
  for (int i = 0; next[next[i]] != i; ) {
    if (is_ear(i, next[i], next[next[i]])) {
      cout << i << " " << next[i] << " " << next[next[i]] << endl;
      next[i] = next[next[i]];
    } else i = next[i];
  }
}


// verify


void verify_intersectCC() {
  auto th = 3.141592653589*rand()/(1.0+RAND_MAX);
  auto dx = 1 - 2*rand()/(1.0+RAND_MAX);
  auto dy = 1 - 2*rand()/(1.0+RAND_MAX);
  auto S = [&](point p) {
    point::T c = cos(th), s = sin(th);
    p.x -= dx; p.y -= dy;
    return (point){c * p.x + s * p.y, -s * p.x + c*p.y};
  };
  auto T = [&](circle C) {
    return (circle){ S(C.p), C.r };
  };
  {
    circle C = { {0,0}, 1 };
    circle D = { {2,0}, 1 };
    TEST(intersect(T(C), T(D)).size(), 1); // touch outer
  }
  {
    circle C = { {0,0}, 1 };
    circle D = { {1,0}, 1 };
    TEST(intersect(T(C), T(D)).size(), 2); // properly intersect inner
  }
  {
    circle C = { {0,0}, 2 };
    circle D = { {1,0}, 1 };
    TEST(intersect(T(C), T(D)).size(), 1); // intersect inner
  }
  {
    circle C = { {0,0}, 2 };
    circle D = { {3,0}, 2 };
    TEST(intersect(T(C), T(D)).size(), 2); // properly intersect outer
  }
  {
    circle C = { {0,0}, 3 };
    circle D = { {1,0}, 1 };
    TEST(intersect(T(C), T(D)).size(), 0); // too close
  }
  {
    circle C = { {0,0}, 1 };
    circle D = { {3,0}, 1 };
    TEST(intersect(T(C), T(D)).size(), 0); // too far
  }
}

void verify_three_point_circle() {
  for (int iter = 0; iter < 100; ++iter) {
    auto urand = []() { return rand() / (1.0 + RAND_MAX); };
    point p = {urand(), urand()};
    point q = {urand(), urand()};
    point r = {urand(), urand()};
    circle c = three_point_circle(p, q, r);
    TEST(sign(dot(c.p - p, c.p - p) - dot(c.p - q, c.p - q)), 0);
    TEST(sign(dot(c.p - p, c.p - p) - dot(c.p - r, c.p - r)), 0);
  }
}

void verify_triangulate() {
  vector<point> ps;
  ps.push_back({0, 0});
  ps.push_back({2, 0});
  ps.push_back({2, 2});
  ps.push_back({1, 1});
  ps.push_back({0, 2});
  triangulate(ps);
}

void verify_convex_cut() {
  int n;
  scanf("%d", &n);
  vector<point> ps(n);
  for (int i = 0; i < n; ++i) {
    scanf("%lf %lf", &ps[i].x, &ps[i].y);
  }
  int m;
  scanf("%d", &m);
  for (int i = 0; i < m; ++i) {
    line L;
    scanf("%lf %lf %lf %lf", &L.p.x, &L.p.y, &L.q.x, &L.q.y);
    vector<point> qs = convex_cut(ps, L);
    printf("%f\n", area(qs));
  }
}

int main() {
  /*
  verify_intersectCC();
  verify_three_point_circle();
  verify_triangulate();
  */
  verify_convex_cut();
}