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:
/*
幾何
https://gist.github.com/zeptometer/3719669
複素数平面による幾何ライブラリ←もっと短くなる可能生アリ
http://osrehun.hatenadiary.jp/entry/2016/12/31/145827

*/
#include <bits/stdc++.h>
using namespace std;

using DD=double;


#define EPS 1e-10
#define eq(a,b) (abs( (a) - (b) )<EPS)
const DD PI=acosl(-1.0);
constexpr DD INF=1LL<<62;

//点
using P=complex<DD>;
//ベクトル
using V=P;
//線分
struct Segment{
    P a,b;
    Segment()=default;
    Segment(P a,P b) :a(a),b(b){}
    Segment(DD ax,DD ay,DD bx,DD by):a(ax,ay),b(bx,by){}

};
//直線
using Line=Segment;
//円
struct Circle{
    P p;
    DD r;
    Circle()=default;
    Circle(P p,DD r):p(p),r(r){}
};
using Polygon=vector<P>;

//++++++++++++++++基本計算++++++++++++++//
inline DD torad(const DD &deg){return deg*PI/180;}
inline DD todeg(const DD &rad){return rad*180/PI;}
//内積
inline DD dot(const V &a,const V &b){
    return real(a*conj(b));
}
//外積
inline DD cross(const V &a,const V &b){
    return imag(conj(a)*b);
}
//ベクトルvを反時計回りにr度回転
inline V rotate(const V &v,const DD r){
    return v*V(cos(r),sin(r));
}
inline bool xy(const P &a,const P &b){
    if(real(a)+EPS<=real(b)) return true;
    if(eq(real(a),real(b)) && imag(a)+EPS<imag(b)) return true;
    return false;
}
inline bool yx(const P &a,const P &b){
    if(imag(a)+EPS<imag(b)) return true;
    if(eq(imag(a),imag(b)) && real(a)+EPS<real(b)) return true;
    return false;
}

//++++++++++++++++平行や直交+++++++++++++++//
inline bool isOrthogonal(const V &a,const V &b){
    return eq(dot(a,b),0.0);
}
inline bool isOrthogonal(const Segment &a,const Segment &b){
    return eq(dot(a.a-a.b,b.a-b.b),0);
}
inline bool isParallel(const V &a,const V &b){
    return eq(cross(a,b),0.0);
}
inline bool isParallel(const Segment &a,const Segment &b){
    return eq(cross(a.a-a.b,b.a-b.b),0);
}
//線分a-bに対してcがどの位置にあるか
//ccwの簡略版 反時計回り:1 時計回り:-1 直線上:0
inline int ccw(const P &a,const P &b,const P &c){
    DD cr=cross(b-a,c-a);
    if(cr>EPS) return 1;
    if(cr<-EPS) return -1;
    return 0;
}

//線分a-bに対してcがどの位置にあるか
//反時計回り:1　時計回り:-1 直線上(a,b,c:-2 a,c,b:0 c,a,b:2) 
inline int ccwH(P a,P b,P c){
    b-=a;c-=a;
    if(cross(b,c)>EPS) return 1;
    if(cross(b,c)<-EPS) return -1;
    if(dot(b,c)<-EPS) return 2;
    if(norm(b)<norm(c)) return -2;
    return 0;
}


//+++++++++++++++射影+++++++++++++++++++++//
inline P project(const P &p,const Segment &s){
    V base=s.b-s.a;
    DD r=dot(p-s.a,base)/norm(base);
    return s.a+base*r;
}
inline P reflect(const P &p,const Segment &s){
    return p+(project(p,s)-p)*2.0;
}
/*++++++++++点との距離++++++++++++++++++*/
//点と直線の距離
inline DD dis(const P &p,const Line &l){return abs(cross(l.b-l.a,p-l.a))/abs(l.b-l.a);}
//点と線分の距離
inline DD disPS(const P &p,const Segment &s){
    if( dot(s.b-s.a,p-s.a)<0.0 ) return abs(p-s.a);
    if( dot(s.a-s.b,p-s.b)<0.0 ) return abs(p-s.b);
    return dis(p,s); //点と直線の距離
}


//+++++++++++++++線分と直線+++++++++++++++++//

//線分a-b,c-dは交差するか?
inline bool intersect(const P &a,const P &b,const P &c,const P &d){
    return(ccwH(a,b,c)*ccwH(a,b,d)<=0 && ccwH(c,d,a)*ccwH(c,d,b)<=0);
}
//線分s,tは交差するか？
inline bool intersect(const Segment &s,const Segment &t){
    return intersect(s.a,s.b,t.a,t.b);
}
//線分と線分の交点
//これをやる前にintersectで判定
inline P crossPoint(const Segment &s,const Segment &t){
    V base=t.b-t.a;
    DD d1=abs(cross(base,s.a-t.a));
    DD d2=abs(cross(base,s.b-t.a));
    DD r=d1/(d1+d2);
    return s.a+(s.b-s.a)*r;
}
//線分と線分の距離
inline DD dis(const Segment &s,const Segment t){
    if(intersect(s,t)) return 0.0;
    return min(min(disPS(t.a,s),disPS(t.b,s)),min(disPS(s.a,t),disPS(s.b,t)) );
}

//+++++++++++円++++++++++++++++//

//円cと直線lの交点
//abs(l,c.p)<c.r+EPSが必要
pair<P,P> crossPoint(const Line &l,const Circle &c){
    P pr=project(c.p,l);
    V e=(l.b-l.a)/(abs(l.b-l.a));
    DD base=sqrt(c.r*c.r-norm(pr-c.p));
    return make_pair(pr+e*base,pr-e*base);
}
//線分sと円cの交点
vector<P> crossPointSC(const Segment &s,const Circle &c){
    vector<P> ret;
    if(dis(c.p,s)>=c.r+EPS) return ret;
    auto p=crossPoint(s,c);
    if(dot(p.first-s.a,s.b-s.a)>0 && dot(p.first-s.b,s.a-s.b)>0) ret.push_back(p.first);
    if(dot(p.second-s.a,s.b-s.a)>0 && dot(p.second-s.b,s.a-s.b)>0) ret.push_back(p.second);
    if(xy(s.a,s.b)) sort(ret.begin(),ret.end(),xy);
    else sort(ret.rbegin(),ret.rend(),xy);
    return ret;
}

//共通接線の数
//離れている:4 外接:3 交わる:2 内接:1 内包:0
inline int intersect(const Circle &a,const Circle &b){
    DD d=abs(a.p-b.p);
    if(d>a.r+b.r+EPS) return 4;
    if(eq(d,a.r+b.r)) return 3;
    if(eq(d,abs(a.r-b.r))) return 1;
    if(d<abs(a.r-b.r)-EPS) return 0;
    return 2;
}

//円c1と円c2の交点
//これを使う前に交点があるかどうかを判定する
vector<P> crossPoint(const Circle &a,const Circle &b){
    vector<P> ret;
    if(abs(a.p-b.p)<a.r+b.r+EPS) return ret;
    DD d=abs(a.p-b.p);
    DD s=acos((a.r*a.r+d*d-b.r*b.r)/(2*a.r*d));
    DD t=arg(b.p-a.p);
    if(eq(s,0)) ret.emplace_back(a.p+polar(a.r,t+s));
    else ret.emplace_back(a.p+polar(a.r,t+s)),ret.emplace_back(a.p+polar(a.r,t-s));
    return ret;
}

//pがcの外にあるかの判定が必要
vector<P> TanLine(const P &p,const Circle &c){
    vector<P> ret;
    DD d=abs(p-c.p);
    if(d<=c.r-EPS) return ret;
    if(eq(d,c.r)){
        ret.push_back(p);
        return ret;
    } 
    return crossPoint(c,Circle(p,sqrt(d*d-c.r*c.r)));
}
//https://ei1333.github.io/luzhiled/snippets/geometry/template.html
//↑すごい。丸写し
//円c1,c2の共通接線
//接点をつないで線にしている(１個だけ追加するときに注意)
vector<Line> TanLine(Circle a,Circle b){
    vector<Line> ret;
    if(a.r<b.r) swap(a,b);
    DD g=abs(a.p-b.p);
    if(eq(g,0)) return ret;
    V u=(b.p-a.p)/g;
    V v=rotate(u,PI*0.5);
    for(DD s:{-1,1}){
        DD h=(a.r+s*b.r)/g;
        if(eq(1-h*h,0)){
            ret.emplace_back(a.p+u*a.r,a.p+(u+v)*a.r);
        }else if(1-h*h>0){
            V uu=u*h,vv=v*sqrt(1-h*h);
            ret.emplace_back(a.p+(uu+vv)*a.r,b.p-(uu+vv)*b.r*s);
            ret.emplace_back(a.p+(uu-vv)*a.r,b.p-(uu-vv)*b.r*s);
        }
    }
    return ret;
}

/*+++++++++++++++++++三角形+++++++++++++++++*/
//外心
//isParallel()を使って判定を忘れずに
P circumcenter(const P &a,const P &b,const P &c){
    P ab=(a+b)/2.0,bc=(b+c)/2.0;
    Segment s(ab,ab+polar(1.0,arg(b-a)+PI*0.5));
    Segment t(bc,bc+polar(1.0,arg(c-b)+PI*0.5));
    return crossPoint(s,t);
}

/*+++++++++++++++++++多角形+++++++++++++++++++*/
//IN:2 ON:1 OUT:0
//点がどの位置にあるか
int contains(const P &p,const Polygon &g){
    int n=(int)g.size();
    bool x=false;
    for(int i=0;i<n;i++){
        V a=g[i]-p,b=g[(i+1)%n]-p;
        if(eq(cross(a,b),0) && dot(a,b)<EPS) return 1;
        if(imag(a)>imag(b)) swap(a,b);
        if(imag(a)<EPS && EPS<imag(b) && cross(a,b)>EPS) x=!x;
    }
    return (x?2:0);
}
//凸性判定
bool isConvex(const Polygon &g){
    int n=(int)g.size();
    int flag=0;
    int t;
    for(int i=0;i<n;i++){
        V a(g[(i+1)%n]-g[i]),b(g[(i+2)%n]-g[i]);
        if(cross(a,b)>EPS) t=1;
        else if(cross(a,b)<-EPS) t=-1;
        else continue;
        if(flag==-t) return false;
        flag=t;
    }
    return true;
}

//凸包　アンドリューのアルゴリズム
//https://github.com/drken1215/algorithm/blob/master/Geometry/All.cpp←螺旋本より早そう
//j=1:返上の点を含まない　j=-1:含む
//反時計回りの多角形を返す
//sはソートされる
Polygon ConvexHull(Polygon &s,const int j){
    int sz=(int)s.size();
    if(sz<3) return s;
    sort(s.begin(),s.end(),yx);

    int n=0;
    Polygon res(2*sz);
    for(int i=0;i<sz;i++){
        while(n>=2 && cross(res[n-1]-res[n-2],s[i]-res[n-2])<EPS*j){
            n--;
        }
        res[n]=s[i];
        n++;
    }
    int t=n+1;
    for(int i=sz-2;i>=0;i--){
        while(n>=t && cross(res[n-1]-res[n-2],s[i]-res[n-2])<EPS*j){
            n--;
        }
        res[n]=s[i];
        n++;
    }
    res.resize(n-1);
    return res;
}

//符号付き面積
//反時計回りの図形なら正
//https://imagingsolution.net/math/calc_n_point_area/
DD Area(const Polygon &g){
    DD ret=0.0;
    int n=(int)g.size();
    for(int i=0;i<n;i++){
        ret+=cross(g[i],g[(i+1)%n]);
    }
    return ret/2.0L;
}

//反時計回り
//理解が浅い←大体分かった（本当か？）
DD Diameter(Polygon g){
    g=ConvexHull(g,1);
    int gz=g.size();
    int m=0,M=0;
    for(int i=1;i<gz;i++){
        if(imag(g[i])<imag(g[m])) m=i;
        if(imag(g[i])>imag(g[M])) M=i;
    }
    DD ret=0;
    int sm=m,sM=M;
    while(m!=sM || M!=sm){
        ret=max(ret,norm(g[m]-g[M]));
        if(cross(g[(m+1)%gz]-g[m],g[(M+1)%gz]-g[M])<0) m=(m+1)%gz;
        else M=(M+1)%gz;
    }
    return sqrt(ret);
}

//凸多角形gをlで切断
//l.p1-l.p2の左側
//gは反時計回り→反時計回りで返す
//時計回り→時計回り
Polygon ConvexCut(const Polygon &g,const Line &l){
    Polygon ret;
    int gz=(int)g.size();
    for(int i=0;i<gz;i++){
        P now=g[i],next=g[(i+1)%gz];
        if(ccw(l.a,l.b,now)>=0) ret.push_back(now);
        if(ccw(l.a,l.b,now)*ccw(l.a,l.b,next)<0){
            ret.push_back(crossPoint(Line(now,next),l));
        }
    }
    return ret;
}

inline DD calc(const P &a,const P &b,const DD &r,const bool triangle){
    if(triangle) return cross(a,b);
    else return r*r*arg(b-a);
}

DD calcArea(const DD &r,const P &a,const P &b){
    if(eq(abs(a-b),0)) return 0;
    bool ina=abs(a)<r+EPS;
    bool inb=abs(b)<r+EPS;
    if(ina && inb) return cross(a,b);
    auto cr=crossPointSC(Segment(a,b),Circle((0,0),r));
    if(cr.empty()) return calc(a,b,r,false);
    auto s=cr[0],t=cr.back();
    return calc(s,t,r,true)+calc(a,s,r,ina)+calc(t,b,r,inb);
}

//円と多角形の共通部分の面積
//http://drken1215.hatenablog.com/entry/2020/02/02/091000
DD Area(const Circle &c,const Polygon &g){
    DD ret=0.0;
    int gz=g.size();
    if(gz<3) return ret;
    for(int i=0;i<gz;i++){
        P a=g[i]-c.p,b=g[(i+1)%gz]-c.p;
        ret+=calcArea(c.r,g[i]-c.p,g[(i+1)%gz]-c.p);
    }
    return ret/2.0;
}

//++++なんか凄いの+++++++++++++++

//最近点対
DD RecClosetPair(Polygon::iterator it,const int n){
    if(n<=1) return INF;
    int m=n/2;
    DD x=real(it[m]);
    DD d=min(RecClosetPair(it,m),RecClosetPair(it+m,n-m));
    inplace_merge(it,it+m,it+n,yx);
    Polygon v;
    for(int i=0;i<n;i++){
        if(abs(real(it[i])-x)>=d) continue;
        for(int j=0;j<v.size();j++){
            DD dy=imag(it[i])-imag(v[v.size()-1-j]);
            if(dy>=d) break;
            DD dx=real(it[i])-real(v[v.size()-1-j]);
            d=min(d,sqrt(dx*dx+dy*dy));
        }
        v.push_back(it[i]);
    }
    return d;
}

DD ClosetPair(Polygon g){
    sort(g.begin(),g.end(),xy);
    return RecClosetPair(g.begin(),g.size());
}




signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr); 
    cout<<fixed<<setprecision(10);

    int n;
    cin>>n;
    Polygon g;
    for(int i=0;i<n;i++){
        DD x,y;
        cin>>x>>y;
        g.emplace_back(x,y);
    }
    int Q;
    cin>>Q;
    while(Q--){
        DD x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        Line l(x1,y1,x2,y2);
        printf("%.10lf\n",Area(ConvexCut(g,l)));
    }
}