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;

namespace arithmetic {
  template<typename T> class Addition {
  public:
    template<typename V> T operator+(const V& v) const {
      return T(static_cast<const T&>(*this)) += v;
    }
  };

  template<typename T> class Subtraction {
  public:
    template<typename V> T operator-(const V& v) const {
      return T(static_cast<const T&>(*this)) -= v;
    }
  };

  template<typename T> class Multiplication {
  public:
    template<typename V> T operator*(const V& v) const {
      return T(static_cast<const T&>(*this)) *= v;
    }
  };

  template<typename T> class Division {
  public:
    template<typename V> T operator/(const V& v) const {
      return T(static_cast<const T&>(*this)) /= v;
    }
  };

  template<typename T> class Modulus {
  public:
    template<typename V> T operator%(const V& v) const {
      return T(static_cast<const T&>(*this)) %= v;
    }
  };
}

template<typename T> class IndivisibleArithmetic : public arithmetic::Addition<T>, public arithmetic::Subtraction<T>, public arithmetic::Multiplication<T> {};

template<typename T> class Arithmetic : public IndivisibleArithmetic<T>, public arithmetic::Division<T> {};

template<typename T> class Ordered {
public:
  template<typename V> bool operator==(const V& v) const {
    return !(static_cast<T>(v) < static_cast<const T&>(*this) || static_cast<const T&>(*this) < static_cast<T>(v));
  }
  
  template<typename V> bool operator!=(const V& v) const {
    return static_cast<T>(v) < static_cast<const T&>(*this) || static_cast<const T&>(*this) < static_cast<T>(v);
  }

  template<typename V> bool operator>(const V& v) const {
    return static_cast<T>(v) < static_cast<const T&>(*this);
  }

  template<typename V> bool operator<=(const V& v) const {
    return !(static_cast<T>(v) < static_cast<const T&>(*this));
  }

  template<typename V> bool operator>=(const V& v) const {
    return !(static_cast<const T&>(*this) < static_cast<T>(v));
  }
};

template<typename T> inline T gcd(T a, T b) {
  return __gcd(a, b);
}

template<typename T> inline T lcm(T a, T b) {
  return a / gcd(a, b) * b;
}

template<typename T> inline T floor(T a, T b) {
  return floor(a / b) * b <= a ? floor(a / b) : floor(a / b) - 1;
}

template<typename T> inline T ceil(T a, T b) {
  return floor(a + b - 1, b);
}

template<typename T> inline T round(T a, T b) {
  return floor(a + b / 2);
}

template<typename T> inline T mod(T a, T b) {
  return a - floor(a, b) * b;
}

template<typename T> inline T factorial(T n) {
  return n <= 1 ? 1 : factorial(n - 1) * n;
}

class Real : public Arithmetic<Real>, public arithmetic::Modulus<Real>, public Ordered<Real> {
private:
  static long double EPS;
  long double val;

  operator long double() const {
    return val;
  }

public:
  Real() {}

  Real(long double val) : val(val) {}

  Real operator-() const {
    return -val;
  }

  template<typename T> Real operator+=(const T& r) {
    val += static_cast<long double>(r);
    return *this;
  }

  template<typename T> Real operator-=(const T& r) {
    val -= static_cast<long double>(r);
    return *this;
  }

  template<typename T> Real operator*=(const T& r) {
    val *= static_cast<long double>(r);
    return *this;
  }

  template<typename T> Real operator/=(const T& r) {
    val /= static_cast<long double>(r);
    return *this;
  }

  template<typename T> Real operator%=(const T& r) {
    return *this = mod(*this, static_cast<Real>(r));
  }

  template<typename T> Real operator-(const T& v) const {
    return Real(*this) -= v;
  }

  template<typename T> Real operator*(const T& v) const {
    return Real(*this) *= v;
  }

  template<typename T> Real operator/(const T& v) const {
    return Real(*this) /= v;
  }

  template<typename T> bool operator<(const T r) const {
    return val < static_cast<long double>(r) - EPS;
  }

  Real abs() const {
    return std::abs(val);
  }

  Real sqrt() const {
    return std::sqrt(val);
  }

  long double toLongDouble() const {
    return val;
  }
};

long double Real::EPS = 1e-10;

inline ostream& operator<<(ostream& os, const Real& a) {
  os << fixed << setprecision(15) << a.toLongDouble();
  return os;
}

inline istream& operator>>(istream& is, Real& a) {
	long double n;
	is >> n;
	a = n;
	return is;
}

Real floor(const Real& r) {
  return floor(r.toLongDouble());
}

class Point : public Arithmetic<Point>, public Ordered<Point> {
public:
  Real x, y;

  Point() {}

  Point(const Real& x) : x(x), y(0) {}

  Point(const Real& x, const Real& y) : x(x), y(y) {}

  Point operator+=(const Point& p) {
    x += p.x;
    y += p.y;
    return *this;
  }

  Point operator-=(const Point& p) {
    x -= p.x;
    y -= p.y;
    return *this;
  }

  Point operator*=(const Point& p) {
    Real xx = x * p.x - y * p.y;
    y = x * p.y + y * p.x;
    x = xx;
    return *this;
  }

  Point operator*=(const Real& r) {
    x *= r;
    y *= r;
    return *this;
  }

  Point operator/=(const Point& p) {
    Real nrm = p.norm();
    Real xx = (x * p.x + y * p.y) / nrm;
    y = (y * p.x - x * p.y) / nrm;
    x = xx;
    return *this;
  }

  Point operator/=(const Real& r) {
    x /= r;
    y /= r;
    return *this;
  }

  bool operator<(const Point& p) const {
    return (x == p.x) ? y < p.y : x < p.x;
  }

  Real norm() const {
    return x * x + y * y;
  }

  Real abs() const {
    return norm().sqrt();
  }

  Point conj() const {
    return Point(x, -y);
  }
};

inline Point operator*(const Real& real, const Point& point) {
  return point * real;
}

inline Point operator/(const Real& real, const Point& point) {
  return point / real;
}

inline ostream& operator<<(ostream& os, const Point& point) {
	os << point.x << " " << point.y;
	return os;
}

inline istream& operator>>(istream& is, Point& point) {
  Real x, y;
	is >> x >> y;
	point = Point(x, y);
	return is;
}

class Line {
public:
  Point a, b;

  Line() {}

  Line (const Point& a, const Point& b) : a(a), b(b) {}

  bool operator==(const Line& line) const {
    return ((line.vec() / vec()).y == 0) && (((line.a - a) / vec()).y == 0);
  }

  Point vec() const {
    return b - a;
  }
};

inline ostream& operator<<(ostream& os, const Line& line) {
	os << line.a << " " << line.b;
	return os;
}

inline istream& operator>>(istream& is, Line& line) {
  Point a, b;
  is >> a >> b;
  line = Line(a, b);
  return is;
}

class Segment : public Line, public Ordered<Segment> {
public:
  Segment() {}

  Segment (const Point& a, const Point& b) : Line(a, b) {}

  bool operator<(const Segment& segment) const {
    return a == segment.a ? b < segment.b : a < segment.a;
  }
};

enum CCW{LEFT = 1, RIGHT = 2, BACK = 4, FRONT = 8, ON = 16};

int ccw(const Point& a, const Point& b, const Point& c) {
  Point p = (c - a) / (b - a);
  if (p.y > 0) return LEFT;
  if (p.y < 0) return RIGHT;
  if (p.x < 0) return BACK;
  if (p.x > 1) return FRONT;
  return ON;
}

int ccw(const Segment& segment, const Point& point) {
  return ccw(segment.a, segment.b, point);
}

int ccw(const Line& line, const Point& point) {
  int res = ccw(line.a, line.b, point);
  if (res == BACK || res == FRONT) res = ON;
  return res;
}

class Polygon : public vector<Point> {
public:
  Polygon() {}

  Polygon(int n) : vector<Point>(n) {}

  Polygon(const initializer_list<Point>& p) : vector<Point>(p) {}

  Polygon(const vector<Point>& p) : vector<Point>(p) {}

  vector<Segment> getSides() const {
    if (size() <= 1u) return {};
    vector<Segment> res;
    Point pre = back();
    for (const auto& point : *this) {
      res.emplace_back(pre, point);
      pre = point;
    }
    return res;
  }

  vector<array<Point, 3>> getCorners() const {
    if (size() <= 2u) return {};
    vector<array<Point, 3>> res;
    Point pre1 = *(end() - 2), pre2 = back();
    for (const auto& point : *this) {
      res.emplace_back(array<Point,3>({{pre1, pre2, point}}));
      pre1 = pre2;
      pre2 = point;
    }
    return res;
  }

  Point& operator[](int i) {
    return vector::operator[](mod(i, (int)size()));
  }

  const Point& operator[](int i) const {
    return vector::operator[](mod(i, (int)size()));
  }

  template<bool strict = false> bool cover(const Point& point) const {
    bool res = false;
    for (auto& side : getSides()) {
      if (ccw(side, point) == ON) return strict ? false : true;
      if (side.a.y > side.b.y) std::swap(side.a, side.b);
      if (side.a.y <= point.y && point.y < side.b.y && ((side.b - point) / (side.a - point)).y > 0) res = !res;
    }
    return res;
  }
};

inline Real area(const Segment& segment) {
  return (segment.a.x * segment.b.y - segment.a.y * segment.b.x) / 2;
}

inline Real area(const Polygon& polygon) {
  auto side = polygon.getSides();
  auto f = [](const Real& r, const Segment& segment){return r + area(segment);};
  return accumulate(side.begin(), side.end(), Real(0), f);
}


template<bool strict = false> inline bool intersect(const Line& line1, const Line& line2) {
  if (strict) return (line1.vec() / line2.vec()).y != 0;
  return ((line1.vec() / line2.vec()).y != 0) || (line1 == line2);
}

template<bool strict = false> inline bool intersect(const Line& line, const Segment& segment) {
  Point p1 = (segment.a - line.a) / line.vec(), p2 = (segment.b - line.a) / line.vec();
  if (strict) return p1.y * p2.y < 0;
  return p1.y * p2.y <= 0;
}

template<bool strict = false> inline bool intersect(const Segment& segment, const Line& line) {
  return intersect(line, segment);
}

template<bool strict = false> inline bool intersect(const Segment& segment1, const Segment& segment2) {
  int ccw1 = ccw(segment1, segment2.a) | ccw(segment1, segment2.b);
  int ccw2 = ccw(segment2, segment1.a) | ccw(segment2, segment1.b);
  if (strict) return (ccw1 & ccw2) == (LEFT | RIGHT);
  return ((ccw1 & ccw2) == (LEFT | RIGHT)) || ((ccw1 | ccw2) & ON);
}

inline Point crossPoint(const Line& line1, const Line& line2) {
  return line1.a + line1.vec() * ((line2.a - line1.a) / line2.vec()).y / (line1.vec() / line2.vec()).y;
}

template<bool strict = true> class ConvexPolygon : public Polygon {
public:
  ConvexPolygon() {}

  ConvexPolygon(int n) : Polygon(n) {}

  ConvexPolygon(vector<Point> points) {
    int flag = ~(strict ? LEFT : LEFT | FRONT);
    sort(points.begin(), points.end());
    for (int i = 0; i < (int)points.size(); emplace_back(points[i++])) {
      while (size() > 1u && ccw(*(end() - 2), back(), points[i]) & flag) pop_back();
    }
    for (int i = points.size() - 2, r = size(); i >= 0; emplace_back(points[i--])) {
      while ((int)size() > r && ccw(*(end() - 2), back(), points[i]) & flag) pop_back();
    }
    pop_back();
  }

  Real diameter() {
    auto sides = getSides();
    int i = min_element(sides.begin(), sides.end()) - sides.begin();
    int j = max_element(sides.begin(), sides.end()) - sides.begin();
    sides.insert(sides.end(), sides.begin(), sides.end());
    Real res = 0;
    for (int k = 0; k < 2 * size(); ++k) {
      if ((sides[i].vec() / sides[j].vec()).y >= 0) ++i;
      else ++j;
      res = max(res, (sides[i].a - sides[j].a).abs());
    }
    return res;
  }

  ConvexPolygon cut(const Line& line) {
    ConvexPolygon res;
    auto sides = getSides();
    for (const auto& side : sides) {
      if (ccw(line, side.a) != RIGHT) res.push_back(side.a);
      if (intersect<true>(line, side)) res.push_back(crossPoint(line, side));
    }
    return res;
  }
};

int main() {
  int n;
  cin >> n;
  ConvexPolygon<> convexPolygon(n);
  for (auto& p : convexPolygon) cin >> p;
  int q;
  cin >> q;
  for (int i = 0; i < q; ++i) {
    Line line;
    cin >> line;
    cout << area(convexPolygon.cut(line)) << endl;
  }
}