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<cmath>
#include<algorithm>
#include<cassert>
////////////////////
// ?????°
const double EPS = 1e-9;                // |EPS|???????????°???0??¨????????±???
////////////////////
// ?§???????
struct Point {
  double x, y;
  Point(const double d = 0.0) : x(d), y(d) {}
  Point(const double x, const double y) : x(x), y(y) {}
};
struct Segment {
  Point initial, terminal;
  Segment(const Point& initial, const Point& terminal) : initial(initial), terminal(terminal) {}
  Segment(const double x1, const double y1, const double x2, const double y2) : initial(x1, y1), terminal(x2, y2) {}
};
struct Line {
  Point initial, terminal;
  Line(const Point& initial, const Point& terminal) : initial(initial), terminal(terminal) {}
  Line(const double x1, const double y1, const double x2, const double y2) : initial(x1, y1), terminal(x2, y2) {}
  Line(const Segment& s) : initial(s.initial), terminal(s.terminal) {}
};
////////////////////
// ????£?
bool relative_equal(const double d1, const double d2) {return d1 == 0 ? std::abs(d2) < EPS : std::abs((d1 - d2) / d1) < EPS;}
// ??????????????????????????????
bool operator==(const Point& lhs, const Point& rhs) {return relative_equal(lhs.x, rhs.x) && relative_equal(lhs.y, rhs.y);}
bool operator<(const Point& lhs, const Point& rhs) {return relative_equal(lhs.x, rhs.x) ? lhs.y < rhs.y : lhs.x < rhs.x;}
bool operator>(const Point& lhs, const Point& rhs) {return relative_equal(lhs.x, rhs.x) ? lhs.y > rhs.y : lhs.x > rhs.x;}
bool operator!=(const Point& lhs, const Point& rhs) {return !(lhs == rhs);}
bool operator<=(const Point& lhs, const Point& rhs) {return !(lhs > rhs);}
bool operator>=(const Point& lhs, const Point& rhs) {return !(lhs < rhs);}
const Point operator+(const Point& lhs, const Point& rhs) {return Point(lhs.x + rhs.x, lhs.y + rhs.y);}
const Point operator-(const Point& lhs, const Point& rhs) {return Point(lhs.x - rhs.x, lhs.y - rhs.y);}
const Point operator*(const Point& lhs, const Point& rhs) {return Point(lhs.x * rhs.x, lhs.y * rhs.y);}
const Point operator/(const Point& lhs, const Point& rhs) {return Point(lhs.x / rhs.x, lhs.y / rhs.y);}
const Point operator-(const Point& p) {return Point(-p.x, -p.y);}
// ???
double abs(const Point& p) {return std::hypot(p.x, p.y);}
double norm(const Point& p) {return p.x * p.x + p.y * p.y;}
double dot(const Point& a, const Point& b) {return a.x * b.x + a.y * b.y;}
double cross(const Point& a, const Point& b) {return a.x * b.y - a.y * b.x;}
// const Point normalize(const Point& p) {return p / abs(p);}
// ??????
// Segment shrink(const Segment& s, const double d = EPS) {
//   Point p = (s.terminal - s.initial) * d;
//   return Segment(s.initial + p, s.terminal - p);
// }
// ???
bool parallel(const Line& l1, const Line& l2) {return std::abs(cross(l2.terminal - l2.initial, l1.terminal - l1.initial)) < EPS;}
bool orthogonal(const Line& l1, const Line& l2) {return std::abs(dot(l2.terminal - l2.initial, l1.terminal - l1.initial)) < EPS;}
// ??????????????¢???
enum POSITION {ONLINE_FRONT = -2, CLOCKWISE, ON_SEGMENT, COUNTER_CLOCKWISE, ONLINE_BACK}; 
POSITION ccw(const Point& a, const Point& b, const Point& p) {
  Point v1 = b - a;
  Point v2 = p - a;
  if(cross(v1, v2) >= EPS) return COUNTER_CLOCKWISE;
  if(cross(v1, v2) <= -EPS) return CLOCKWISE;
  if(dot(v1, v2) <= -EPS) return ONLINE_BACK;
  if(norm(v1) < norm(v2)) return ONLINE_FRONT;              // ????????????: norm(v1)<norm(v2)+EPS?????¨WrongAnswer
  return ON_SEGMENT;
}
// ????????????
bool intersect(const Point& p1, const Point& p2) {return p1 == p2;}
bool intersect(const Point& p, const Segment& s) {return abs(p - s.initial) + abs(p - s.terminal) - abs(s.initial - s.terminal) <= EPS;}
bool intersect(const Segment& s, const Point& p) {return intersect(p, s);}
bool intersect(const Point& p, const Line& l) {return !parallel(Line(p, l.initial), Line(p, l.terminal));}
bool intersect(const Line& l, const Point& p) {return intersect(p, l);}
bool intersect(const Segment& s1, const Segment& s2) {
  return ccw(s1.initial, s1.terminal, s2.initial) * ccw(s1.initial, s1.terminal, s2.terminal) <= 0
      && ccw(s2.initial, s2.terminal, s1.initial) * ccw(s2.initial, s2.terminal, s1.terminal) <= 0;
}
bool intersect(const Segment& s, const Line& l) {
  auto v1 = l.terminal - l.initial;
  auto v2 = s.initial  - l.initial;
  auto v3 = s.terminal - l.initial;
  return cross(v1, v2) * cross(v1, v3) <= EPS;
}
bool intersect(const Line& l, const Segment& s) {return intersect(s, l);}
bool intersect(const Line& l1, const Line& l2) {return !parallel(l1, l2) || intersect(l1.initial, l2);}
// ???????§????
Point projection(const Point& p, const Line& l) {
  auto v = l.initial - l.terminal;
  return l.initial + dot(p - l.initial, v) / norm(v) * v;
}
Point projection(const Line& l, const Point& p) {return projection(p, l);}
Point reflection(const Point& p, const Line& l) {return p + 2 * (projection(p, l) - p);}
Point reflection(const Line& l, const Point& p) {return reflection(p, l);}
// ?????¢
double distance(const Point& p1, const Point& p2) {
  auto p = p1 - p2;
  return hypot(p.x, p.y);
}
double distance(const Point& p, const Segment& s) {
  auto r = projection(s, p);
  return intersect(r, s) ? distance(p, r) : std::min(distance(p, s.initial), distance(p, s.terminal));
}
double distance(const Segment& s, const Point& p) {return distance(p, s);}
double distance(const Point& p, const Line& l) {return distance(p, projection(p, l));}
double distance(const Line& l, const Point& p) {return distance(p, l);}
double distance(const Segment& s1, const Segment& s2) {
  return intersect(s1, s2) ? 0.0 : std::min({distance(s1, s2.initial), distance(s1, s2.terminal), distance(s2, s1.initial), distance(s2, s1.terminal)});
}
double distance(const Segment& s, const Line& l) {return intersect(s, l) ? 0.0 : std::min(distance(s.initial, l), distance(s.terminal, l));}
double distance(const Line& l,const Segment& s) {return distance(s, l);}
double distance(const Line& l1, const Line& l2) {return intersect(l1, l2) ? 0.0 : distance(l1.initial, l2);}
// ??????
const Point crosspoint(const Line& l1, const Line& l2) {
  assert(intersect(l1, l2));
  if(parallel(l1, l2)) return l1.initial;                   // ???????????¨???l1????§?????????????
  double A = cross(l1.terminal - l1.initial, l2.terminal - l2.initial);
  double B = cross(l1.terminal - l1.initial, l1.terminal - l2.initial);
  return l2.initial + B / A * (l2.terminal - l2.initial);
}
const Point crosspoint(const Segment& s, const Line& l) {
  assert(intersect(s, l));
  if(parallel(s, l)) return s.initial;
  Point cp = crosspoint(Line(s), l);
  assert(intersect(s, cp));
  return cp;
}
const Point crosspoint(const Line& l, const Segment& s) {return crosspoint(s, l);}
const Point crosspoint(const Segment& s1, const Segment& s2) {
  assert(intersect(s1, s2));
  if(parallel(s1, s2)) {                                    // ???????????¨?????????????????????????????????
    if(intersect(s1.initial,  s2)) return s1.initial;
    if(intersect(s1.terminal, s2)) return s1.terminal;
    if(intersect(s2.initial,  s1)) return s2.initial;
    if(intersect(s2.terminal, s1)) return s2.terminal;
  }
  return crosspoint(Line(s1), Line(s2));
}
// ???????????°??¨
#include<bits/stdc++.h>
using namespace std;
ostream& operator<<(ostream& os, const Point& p) {os<<"point: "; os<<"("<<p.x<<","<<p.y<<")"; return os;}
ostream& operator<<(ostream& os, const Segment& s) {os<<"segment: "; os<<s.initial<<" - "<<s.terminal; return os;}
ostream& operator<<(ostream& os, const Line& l) {os<<"line: "; os<<l.initial<<" - "<<l.terminal; return os;}
////////////////////////////////////////////////////////////////////////////////
// ????§???¢
//   ????????????????????°????????????????????¢???????´????edge(void)???O(????????°)???edge().begin()????????£????????????????????????????????????????????????
#include<vector>
#include<algorithm>
#include<numeric>
#include<utility>
class Polygon {
public:
  // ??¨???
  void add(const Point& p) {
    if(!vertex_.empty()) {
      if(!edge_.empty()) edge_.pop_back();
      edge_.push_back(Segment(vertex_.back(), p));
      edge_.push_back(Segment(p, vertex_.front()));
    }
    vertex_.push_back(p);
  }
  void clear() {
    vertex_.clear();
    edge_.clear();
  };
  // ?????±
  int size() const {return vertex_.size();}
  Point vertex(const int n) const {return vertex_.at(n);}
  Segment edge(const int n) const {return edge_.at(n);}
  const std::vector<Point>& vertex() const {return vertex_;}
  const std::vector<Segment>& edge() const {return edge_;}
  // ??????
  bool touch(const Point& p) const {
    return std::any_of(begin(edge()), end(edge()), [=](const Segment& s) {return ccw(s.initial, s.terminal, p) == ON_SEGMENT;});
  }
  bool intersect(const Point& p) const {
    bool in = false;                    // p=(x,y)??????(INF,y)???????????´?????¨????§???¢??¨????????????????????° mod 2
    for(const auto& e: edge()) {
      if(::intersect(p, e)) return true;
      Point a = e.initial  - p;
      Point b = e.terminal - p;
      if(a.y > b.y) std::swap(a, b);
      if(a.y < EPS && EPS <= b.y && cross(a, b) < EPS) in = !in;
    }
    return in;
  }
  double area() const {
    return std::abs(std::accumulate(begin(edge()), end(edge()), 0.0, [=](const double sum, const Segment& e){return sum + cross(e.initial, e.terminal);})) / 2.0;
  }
  bool convex() const {
    bool positive = false;
    bool negative = false;
    for(int i = 0; i < size(); ++i) {
      auto position = ccw(vertex(i), vertex((i + 1) % size()), vertex((i + 2) % size()));
      positive |= position == CLOCKWISE;
      negative |= position == COUNTER_CLOCKWISE;
      if(negative && positive) return false;
    }
    return true;
  }
  const Polygon cut(const Line& l) const {
    Polygon result;
    for(const auto& e: edge()) {
      if(ccw(l.initial, l.terminal, e.initial) == COUNTER_CLOCKWISE) result.add(e.initial);
      if(::intersect(e, l)) result.add(crosspoint(e, l));
    }
    return result;
  }
private:
  std::vector<Point> vertex_;
  std::vector<Segment> edge_;
};
////////////////////////////////////////////////////////////////////////////////
#include<bits/stdc++.h>
using namespace std;
int main() {
  // Points/Vectors
//   Point p1, p2;
//   cin >> p1.x >> p1.y >> p2.x >> p2.y;
//   int q;
//   for(cin >> q; q > 0; --q) {
//     int x, y;
//     cin >> x >> y;
    // A
//     Point p = projection(Line(p1, p2), Point(x, y));
//     cout << setprecision(10) << fixed << p.x << " " << p.y << endl;
    // B
//     Point p = reflection(Line(p1, p2), Point(x, y));
//     cout << setprecision(10) << fixed << p.x << " " << p.y << endl;
    // C
//     switch(ccw(p1, p2, Point(x, y))) {
//     case COUNTER_CLOCKWISE:
//       cout << "COUNTER_CLOCKWISE" << endl;
//       break;
//     case CLOCKWISE:
//       cout << "CLOCKWISE" << endl;
//       break;
//     case ONLINE_BACK:
//       cout << "ONLINE_BACK" << endl;
//       break;
//     case ONLINE_FRONT:
//       cout << "ONLINE_FRONT" << endl;
//       break;
//     case ON_SEGMENT:
//       cout << "ON_SEGMENT" << endl;
//       break;
//     }
//   }

  // Segments/Lines
//   int n;
//   for(cin >> n; n > 0; --n) {
//     int a, b, c, d, e, f, g, h;
//     cin >> a >> b >> c >> d >> e >> f >> g >> h;
//     Segment s(Point(a, b), Point(c, d));
//     Segment t(Point(e, f), Point(g, h));
//     // A
// //     cout << (parallel(s, t) ? 2 : (orthogonal(s, t) ? 1 : 0)) << endl;
//     // B
// //     cout << (intersect(s, t) ? 1 : 0) << endl;
//     // C
// //     auto cp = crosspoint(s, t);
// //     cout << setprecision(10) << fixed << cp.x << " " << cp.y << endl;
//     // D
// //     cout << setprecision(10) << fixed << distance(s, t) << endl;
//   }

  // Polygon
//   int n;
//   Polygon polygon;
//   for(cin >> n; n > 0; --n) {
//     int x, y;
//     cin >> x >> y;
//     polygon.add(Point(x, y));
//   }
//   // A
// //   cout << setprecision(1) << fixed  << polygon.area() << endl;
//   // B
// //   cout << (polygon.convex() ? 1 : 0) << endl;
//   // C
//   int q;
//   for(cin >> q; q > 0; --q) {
//     int x, y;
//     cin >> x >> y;
//     Point p(x, y);
//     cout << (polygon.touch(p) ? 1 : (polygon.intersect(p) ? 2 : 0)) << endl;
//   }

  // Convex Polygon
  int n;
  Polygon polygon;
  for(cin >> n; n > 0; --n) {
    double x, y;
    cin >> x >> y;
    polygon.add(Point(x, y));
  }
  for(cin >> n; n > 0; --n) {
    double x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    cout << setprecision(10) << fixed << polygon.cut(Line(x1, y1, x2, y2)).area() << endl;
  }
}