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 rep(i,n) for(int i = 0; i < (int)n; i++)

const double eps = 1e-10;
const double inf = 1e+10;
const double pi = acos(-1.0);

struct Point {
  double x, y;
  Point(double x = 0.0, double y = 0.0) : x(x), y(y) {}  
  double norm() {return sqrt(x*x + y*y);}
};

Point operator + (const Point &p, const Point &q) {return Point(p.x + q.x, p.y + q.y);}
Point operator - (const Point &p, const Point &q) {return Point(p.x - q.x, p.y - q.y);}
double operator * (const Point &p, const Point q) {return p.x * q.x + p.y * q.y;}
bool operator == (const Point &p, const Point &q) {return (abs(p.x - q.x) < eps && abs(p.y - q.y) < eps);}
bool operator != (const Point &p, const Point &q) {return !(p == q);}
double cross(const Point &p, const Point &q) {return p.x*q.y - p.y*q.x;}
double dist(const Point &p, const Point &q) {return (p-q).norm();}
bool compx(const Point &p, const Point &q) {return p.x != q.x? p.x < q.x : p.y < q.y;}
bool compy(const Point &p, const Point &q) {return p.y != q.y? p.y < q.y : p.x < q.x;}

struct Segment {
  Point p , q;
  Segment(Point p = Point(0.0,0.0), Point q = Point(0.0,0.0)) : p(p), q(q) {}
};

struct Line {
  double a, b, c;
  Line(double a, double b, double c) : a(a), b(b), c(c) {}
  Line(Point p, Point q) {
    a = q.y - p.y;
    b = p.x - q.x;
    c = q.x * p.y - p.x * q.y;
  }
};

struct Circle {
  double r;
  Point p;
  Circle(Point p = Point(0.0, 0.0), double r = 0.0) : p(p), r(r) {}
};

// 点の直線への射影
Point projection (Point p, Line l) {
  double x = p.x - l.a * (l.a*p.x + l.b*p.y + l.c) / (l.a*l.a + l.b*l.b);
  double y = p.y - l.b * (l.a*p.x + l.b*p.y + l.c) / (l.a*l.a + l.b*l.b);
  return Point(x,y);
}

// 線対称な点
Point reflection(Point p, Line l) {
  double x = p.x - 2.0 * l.a * (l.a*p.x + l.b*p.y + l.c) / (l.a*l.a + l.b*l.b);
  double y = p.y - 2.0 * l.b * (l.a*p.x + l.b*p.y + l.c) / (l.a*l.a + l.b*l.b);
  return Point(x,y);
}

// 点の線分からの回転方向 (1:半時計 -1:時計 2:同一直線後方 -2:同一直線前方 0:線分上)
int ccw(Point p, Point p1, Point p2) {
  p1 = p1 - p; p2 = p2 - p;
  if(cross(p1,p2) > eps) return 1; 
  if(cross(p1,p2) < -eps) return -1; 
  if(p1 * p2 < 0) return 2; 
  if(p1.norm() < p2.norm()) return -2; 
  return 0; 
}

// 点が線分上にあるか判定
bool on_segment(Point p, Segment s) {
  return (ccw(s.p,s.q,p) == 0 ? true : false);
}

// 線分の交差判定
bool segment_segment_cross(const Segment l, const Segment s) {
  return ccw(l.p,l.q,s.p) * ccw(l.p,l.q,s.q) <= 0 && ccw(s.p,s.q,l.p) * ccw(s.p,s.q,l.q) <= 0;
}

// 直線の平行・直交判定 (平行:2 直交:1 その他:0)
int line_parallel_orthogonal(Line l, Line s) {
  if(abs(l.a*s.a + l.b*s.b) < eps) return 1;
  else if(abs(l.a*s.b - l.b*s.a) < eps) return 2;
  else return 0;
}

// 直線と直線の交点 
vector<Point> line_line_cross(Line l, Line s) {
  vector<Point> vp;
  if(line_parallel_orthogonal(l,s) != 2) {
    Point p;
    p.x = (l.b*s.c - s.b*l.c) / (l.a*s.b - s.a*l.b);
    p.y = (-l.a*s.c + s.a*l.c) / (l.a*s.b - s.a*l.b);
    vp.push_back(p);
  }
  return vp;
}

// 点と直線の距離
double point_line_dist(Point p, Line l) {
  return abs(l.a*p.x + l.b*p.y + l.c) / sqrt(l.a*l.a + l.b*l.b);
}

// 点と線分の距離
double point_segment_dist(Point p, Segment s) {
  Point h = projection(p,Line(s.p,s.q));
  if(on_segment(h,s)) return dist(p,h);
  else return min(dist(p,s.p),dist(p,s.q));
}

// 線分と線分の距離
double segment_segment_dist(Segment l, Segment s) {
  if(segment_segment_cross(l,s)) return 0.0;
  else return min({point_segment_dist(l.p,s),point_segment_dist(l.q,s),point_segment_dist(s.p,l),point_segment_dist(s.q,l)});
}

// 直線と直線の距離
double line_line_dist(Line l, Line s) {
  if(line_parallel_orthogonal(l,s) != 2) return 0.0;
  else if(abs(s.a) < eps) return point_line_dist(Point(0.0,-s.c/s.b),l);
  else return point_line_dist(Point(-s.c/s.a,0),l);
}

// 直線と線分の距離
double line_segment_dist(Line l, Segment s) {
  Point a, b;
  if(abs(l.a) < eps) a = Point(0.0,-l.c/l.b), b = Point(1.0,-l.c/l.b);
  else if(abs(l.b) < eps) a = Point(-l.c/l.a,0.0), b = Point(-l.c/l.a,1.0);
  else a = Point(0.0,-l.c/l.b), b = Point(-l.c/l.a,0);

  if(ccw(a,b,s.p) * ccw(a,b,s.q) <= 0) return 0.0;
  else return min(point_line_dist(s.p,l),point_line_dist(s.q,l));
}

// ★円と円の交差判定 (離れる:4 外接:3 交わる:2 内接:1 内包:0)
int circle_circle_pos(Circle c, Circle d) {
  if(dist(c.p,d.p) >= c.r + d.r + eps) return 4;
  else if(abs(dist(c.p,d.p) - c.r - d.r) < eps) return 3;
  else if(dist(c.p,d.p) >= abs(c.r-d.r) + eps) return 2;
  else if(abs(dist(c.p,d.p) - abs(c.r-d.r)) < eps) return 1;
  else return 0; 
}

// ★円と直線の交点
vector<Point> circle_line_cross(Circle c, Line l) {
  vector<Point> vp;
  Point h = projection(c.p,l);

  double d = l.a*c.p.x + l.b*c.p.y + l.c;
  double q = c.r*c.r - d*d / (l.a*l.a + l.b*l.b);
  if(q >= eps) {
    Point p1, p2;
    p1.x = h.x + sqrt(q) * l.b / sqrt(l.a*l.a + l.b*l.b);
    p1.y = h.y - sqrt(q) * l.a / sqrt(l.a*l.a + l.b*l.b);
    p2.x = h.x - sqrt(q) * l.b / sqrt(l.a*l.a + l.b*l.b);
    p2.y = h.y + sqrt(q) * l.a / sqrt(l.a*l.a + l.b*l.b);
    vp.push_back(p1);
    vp.push_back(p2);
  } else if(abs(q) < eps) {
    vp.push_back(h);
  }
  return vp;
} 

// ★円と円の交点
vector<Point> circle_circle_cross(Circle c, Circle d) {
  if(circle_circle_pos(c,d)) {
    Line l(2.0*(c.p.x-d.p.x),2.0*(c.p.y-d.p.y),-c.p.x*c.p.x+d.p.x*d.p.x-c.p.y*c.p.y+d.p.y*d.p.y+c.r*c.r-d.r*d.r);
    return circle_line_cross(c,l);
  } else {
    return vector<Point>();
  }
}

// ★円の点Pを通る接線
vector<Line> tangent_to_circle(Circle c, Point p) {
  if(dist(c.p,p) < c.r - eps) return vector<Line>();
  Point q = p - c.p;
  vector<Point> v = circle_line_cross(c,Line(q.x,q.y,-(q*c.p+c.r*c.r)));
  vector<Line> l;
  for(auto t : v) {
    q = t - c.p;
    l.push_back(Line(q.x,q.y,-(q*c.p+c.r*c.r)));
  }
  return l;
}

// ★円と円の共通接線
vector<Line> common_tangent(Circle c, Circle d) {
  Point da = d.p - c.p;
  vector<Point> tin = circle_line_cross(Circle(Point(0.0,0.0),c.r),Line(da.x,da.y,-c.r*(c.r+d.r)));
  vector<Point> tout = circle_line_cross(Circle(Point(0.0,0.0),c.r),Line(da.x,da.y,-c.r*(c.r-d.r)));
  vector<Line> l;
  for(auto p : tin) {
    vector<Line> lin = tangent_to_circle(c,p+c.p);
    for(auto s : lin) l.push_back(s);
  }
  for(auto p : tout) {
    vector<Line> lout = tangent_to_circle(c,p+c.p);
    for(auto s : lout) l.push_back(s);
  }
  return l;
}

// ★多角形の面積
double polygon_area(vector<Point>& v) {
  int l = v.size();
  if(l <= 2) return 0.0;
  double s = 0.0;
  for(int i = 0; i < l; i++) s += 1/2.0 * cross(v[i],v[(i+1)%l]);
  return s;
}

// ★多角形の凸性
bool polygon_convex(vector<Point>& v) {
  int l = v.size();
  for(int i = 0; i < l; i++) {
    if(cross(v[(i+1)%l]-v[i],v[(i+2)%l]-v[i]) < -eps) return false;
  }
  return true;
} 

// ★点の多角形への包含 (含まれる:2 辺上:1 外:0)
int polygon_inclusion(const vector<Point>& v, const Point p) {
  int l = v.size();
  bool in = false;
  for(int i = 0; i < l; i++) {
    Point a = v[i] - p, b = v[(i+1)%l] - p;
    if(on_segment(Point(0.0,0.0),Segment(a,b))) return 1;
    if(a.y > b.y) swap(a,b);
    if(a.y <= 0 && b.y > 0 && cross(a,b) < 0) in = !in; 
  }
  return in ? 2 : 0;
}

// ★凸包 O(nlogn) (Graham Scan)
vector<Point> convex_hull(vector<Point>& v) {
  int l = v.size();
  sort(v.begin(),v.end(),compx);
  vector<Point> c(2*l);
  int k = 0;
  for(int i = 0; i < l; i++) {
    while(k > 1 && cross(c[k-1]-c[k-2],v[i]-c[k-1]) <= -eps) k--;
    c[k++] = v[i];
  }
  for(int i = l-2, t = k; i >= 0; i--) {
    while(k > t && cross(c[k-1]-c[k-2],v[i]-c[k-1]) <= -eps) k--;
    c[k++] = v[i];
  }
  c.resize(k-1);
  return c;
}

// 凸多角形の切断(左側)
vector<Point> convex_cut(vector<Point>& v, Point a, Point b) {
  int n = v.size();
  vector<Point> res;
  for(int i = 0; i < n; i++) {
    Point now = v[i], next = v[(i+1)%n];
    if(ccw(a,b,now) != -1) res.push_back(now);
    if(ccw(a,b,now)*ccw(a,b,next) < 0) {
      vector<Point> c = line_line_cross(Line(a,b),Line(now,next));
      for(auto p : c) res.push_back(p);
    }
  }
  return res;
}

// ★最遠点距離(キャリパー法) O(n) (凸包を構成する場合O(nlogn))
double convex_diameter(vector<Point>& v) {
  vector<Point> c = convex_hull(v);
  int l = c.size();
  if(l == 2) return (dist(c[0],c[1]));
  int i = 0, j = 0;
  for(int k = 0; k < l; k++) {
    if(!compx(c[i],c[k])) i = k;
    if(compx(c[j],c[k])) j = k;
  }
  double res = 0.0;
  int si = i, sj = j;
  while(i != sj || j != si) {
    res = max(res,dist(c[i],c[j]));
    if(cross(c[(i+1)%l]-c[i],c[(j+1)%l]-c[j]) < 0) i = (i + 1) % l;
    else j = (j + 1) % l;
  }
  return res;
}

// ★最近接点距離 O(nlogn) x座標でsortして渡す.
double closest_pair(vector<Point>::iterator it, int n) {
  if(n <= 1) return inf;
  int m = n / 2;
  double x = it[m].x;
  double d = min(closest_pair(it,m),closest_pair(it+m,n-m));
  inplace_merge(it,it+m,it+n,compy);

  vector<Point> b;
  for(int i = 0; i < n; i++) {
    if(abs(it[i].x-x) >= d) continue;
    for(int j = 0; j < b.size(); j++) {
      double dx = it[i].x - b[b.size()-j-1].x;
      double dy = it[i].y - b[b.size()-j-1].y;
      if(dy >= d) break;
      d = min(d,sqrt(dx*dx+dy*dy));
    }
    b.push_back(it[i]);
  }
  return d;
}

int main() {
  int n;
  cin >> n;
  vector<Point> g(n);
  rep(i,n) cin >> g[i].x >> g[i].y;
  int q;
  cin >> q;
  rep(i,q) {
    Point a, b;
    cin >> a.x >> a.y >> b.x >> b.y;
    vector<Point> r = convex_cut(g,a,b);
    printf("%.9lf\n",polygon_area(r));
  }
  return 0;
}