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 <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

const double EPS = 1e-9;
const double PI = acos(-1);

int sign(double x) {
    if (fabs(x) < EPS) {
        return 0;
    } else if (x > 0) {
        return 1;
    } else {
        return -1;
    }
}

int dcmp(double x, double y) {
    return sign(x - y);
}

struct Vector;
typedef Vector Point;

struct Vector {
    double x;
    double y;

    explicit Vector(double x = 0, double y = 0);

    Vector operator+(const Vector &rhs) const;
    Vector operator-() const;
    Vector operator-(const Vector &rhs) const;
    Vector operator*(double d) const;
    Vector operator/(double d) const;
    double operator*(const Vector &rhs) const;
    double operator^(const Vector &rhs) const;

    bool operator==(const Vector &rhs) const;
    bool operator!=(const Vector &rhs) const;
    bool operator<(const Vector &rhs) const;
    bool operator>(const Vector &rhs) const;
    bool operator<=(const Vector &rhs) const;
    bool operator>=(const Vector &rhs) const;

    friend std::ostream &operator<<(std::ostream &os, const Vector &vector);

    double dot(const Vector &rhs) const;
    double cross(const Vector &rhs) const;
    double length() const;
    double length2() const;
    double angle() const;
    double angle(const Vector &rhs) const;
    Vector rotate(double rad) const;
    Vector rotate90() const;
    Vector rotate90R() const;
    Vector normal() const;
    Vector truncate(double d) const;
    double getDistanceTo(const Point &p) const;

    static bool cmpByAngle(const Vector &a, const Vector &b);
};

struct Line {
    Point a;
    Point b;

    explicit Line(double x1 = 0, double y1 = 0, double x2 = 0, double y2 = 0);
    explicit Line(const Point &a = Point(), const Point &b = Point());

    double getDistanceTo(const Point &p) const;
    Point getIntersection(const Line &rhs) const;
    Point getProjection(const Point &p) const;
    Point getReflection(const Point &p) const;
    bool contains(const Point &p) const;
    bool intersects(const Line &rhs) const;
    bool parallels(const Line &rhs) const;
    bool isPerpendicularTo(const Line &rhs) const;
};

struct Polygon {
    std::vector<Point> points;

    enum class ContainsPoint {
        OUT,
        ONLINE,
        ON_VERTEX,
        IN
    };

    explicit Polygon(const std::vector<Point> &points = std::vector<Point>(0));

    Point &operator[](const int index);

    int size() const;
    double area() const;
    double circumference() const;
    Polygon cutByHalfPlane(const Line &l) const;
};

Vector::Vector(double x, double y) : x(x), y(y) {}

Vector Vector::operator+(const Vector &rhs) const {
    return Vector(x + rhs.x, y + rhs.y);
}

Vector Vector::operator-() const {
    return Vector(-x, -y);
}

Vector Vector::operator-(const Vector &rhs) const {
    return *this + -rhs;
}

Vector Vector::operator*(double d) const {
    return Vector(x * d, y * d);
}

Vector Vector::operator/(double d) const {
    return *this * (1 / d);
}

double Vector::operator*(const Vector &rhs) const {
    return x * rhs.x + y * rhs.y;
}

double Vector::operator^(const Vector &rhs) const {
    return x * rhs.y - rhs.x * y;
}

bool Vector::operator==(const Vector &rhs) const {
    return dcmp(x, rhs.x) == 0 && dcmp(y, rhs.y) == 0;
}

bool Vector::operator!=(const Vector &rhs) const {
    return !(rhs == *this);
}

bool Vector::operator<(const Vector &rhs) const {
    if (dcmp(x, rhs.x) != 0) {
        return dcmp(x, rhs.x) < 0;
    } else {
        return dcmp(y, rhs.y) < 0;
    }
}

bool Vector::operator>(const Vector &rhs) const {
    return rhs < *this;
}

bool Vector::operator<=(const Vector &rhs) const {
    return !(rhs < *this);
}

bool Vector::operator>=(const Vector &rhs) const {
    return !(*this < rhs);
}

std::ostream &operator<<(std::ostream &os, const Vector &vector) {
    os << "(" << vector.x << "," << vector.y << ")";
    return os;
}

double Vector::dot(const Vector &rhs) const {
    return *this * rhs;
}

double Vector::cross(const Vector &rhs) const {
    return *this ^ rhs;
}

double Vector::length() const {
    return sqrt(*this * *this);
}

double Vector::length2() const {
    return *this * *this;
}

double Vector::angle() const {
    return atan2(y, x);
}

double Vector::angle(const Vector &rhs) const {
    return acos((*this * rhs) / length() / rhs.length());
}

Vector Vector::rotate(double rad) const {
    // Rotate counter-clockwise
    return Vector(x * cos(rad) - y * sin(rad), x * sin(rad) + y * cos(rad));
}

Vector Vector::rotate90() const {
    return Vector(-y, x);
}

Vector Vector::rotate90R() const {
    return Vector(y, -x);
}

Vector Vector::normal() const {
    double l = length();
    return Vector(-y / l, x / l);
}

double Vector::getDistanceTo(const Point &p) const {
    return sqrt(pow(x - p.x, 2) + pow(y - p.y, 2));
}

bool Vector::cmpByAngle(const Vector &a, const Vector &b) {
    return dcmp(a.angle(), b.angle()) < 0;
}

Vector Vector::truncate(double d) const {
    double l = length();
    if (sign(l) == 0) {
        return *this;
    }
    d /= l;
    return Vector(x * d, y * d);
}

Line::Line(double x1, double y1, double x2, double y2) : a(x1, y1), b(x2, y2) {}

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

double Line::getDistanceTo(const Point &p) const {
    const Vector &v1 = b - a;
    const Vector &v2 = p - a;
    return fabs(v1 ^ v2 / v1.length());
}

Point Line::getIntersection(const Line &rhs) const {
    if (!intersects(rhs)) {
        return Point();
    }
    Vector u = a - rhs.a;
    Vector v = b - a;
    Vector w = rhs.b - rhs.a;
    double t = (w ^ u) / (v ^ w);
    return a + v * t;
}

Point Line::getProjection(const Point &p) const {
    const Vector &v = b - a;
    return a + v * (v * (p - a) / (v * v));
}

Point Line::getReflection(const Point &p) const {
    return getProjection(p) * 2 - p;
}

bool Line::contains(const Point &p) const {
    Point p1 = a;
    Point p2 = b;
    if (p1 == p) {
        p1 = p1 + (p2 - p1) * 2;
    } else if (p2 == p) {
        p2 = p2 + (p1 - p2) * 2;
    }
    return sign((p2 - p) ^ (p1 - p)) == 0;
}

bool Line::intersects(const Line &rhs) const {
    return sign((a - b) ^ (rhs.a - rhs.b)) != 0;
}

bool Line::parallels(const Line &rhs) const {
    return !intersects(rhs);
}

bool Line::isPerpendicularTo(const Line &rhs) const {
    return sign((b - a) * (rhs.b - rhs.a)) == 0;
}

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

Point &Polygon::operator[](const int index) {
    return points[index];
}

int Polygon::size() const {
    return points.size();
}

double Polygon::area() const {
    if (points.size() < 3) {
        return 0;
    }
    double sum = points.back() ^points.front();
    for (int i = 0; i < (int) points.size() - 1; i++) {
        sum += points[i] ^ points[i + 1];
    }
    return sum / 2;
}

double Polygon::circumference() const {
    if (points.size() < 3) {
        return 0;
    }
    double sum = (points.back() - points.front()).length();
    for (int i = 0; i < (int) points.size() - 1; i++) {
        sum += (points[i] - points[i + 1]).length();
    }
    return sum;
}

Polygon Polygon::cutByHalfPlane(const Line &line) const {
    // Left side of the line
    Polygon res;
    for (int i = 0; i < points.size(); i++) {
        int d1 = sign((line.b - line.a) ^ (points[i] - line.a));
        int d2 = sign((line.b - line.a) ^ (points[(i + 1) % points.size()] - line.a));
        if (d1 >= 0) {
            res.points.push_back(points[i]);
        }
        if (d1 * d2 < 0) {
            res.points.push_back(line.getIntersection(Line(points[i], points[(i + 1) % points.size()])));
        }
    }
    return res;
}

int main() {
//    freopen("data.in", "r", stdin);

    double x, y;
    double x2, y2;
    int n, q;
    while (~scanf("%d", &n)) {
        vector<Point> points;
        points.reserve(n);
        for (int i = 0; i < n; i++) {
            scanf("%lf%lf", &x, &y);
            points.emplace_back(x, y);
        }
        Polygon polygon(points);

        scanf("%d", &q);
        while (q--) {
            scanf("%lf%lf", &x, &y);
            scanf("%lf%lf", &x2, &y2);

            printf("%.10f\n", polygon.cutByHalfPlane(Line(x, y, x2, y2)).area());
        }
    }
    return 0;
}