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;
const double eps=1e-9;
struct dot{
	double x,y;
	double len(){return sqrt(x*x+y*y);}
	dot(double a=0.0,double b=0.0){x=a,y=b;}
	dot operator +(const dot&b)const {return dot(x+b.x,y+b.y);}
	dot operator -(const dot&b)const {return dot(x-b.x,y-b.y);}
	dot operator *(const double&z)const {return dot(x*z,y*z);}
	bool operator <(const dot&b)const {return (y<b.y)||(y==b.y&&x<b.x);}
	bool operator ==(const dot&b)const {return fabs(x-b.x)<eps&&fabs(y-b.y)<eps;}	
	bool operator !=(const dot&b)const {return fabs(x-b.x)>=eps||fabs(y-b.y)>=eps;}
	void read(){scanf("%lf%lf",&x,&y);} 
};
struct line{
	dot x1,x2;
	void read(){x1.read();x2.read();};
	line(dot a=dot(0.0,0.0),dot b=dot(0.0,0.0)){x1=a,x2=b;} 
	dot getdot(){return x2-x1;}
	line change(){
		int flag=x1<x2;
		if (x2.x==x1.x){
			x1=dot(x1.x,-1e9);x2=dot(x2.x,1e9);
			if (!flag)swap(x1,x2);
			return line(x1,x2);
		}
		double k=(x2.y-x1.y)/(x2.x-x1.x),b=x1.y-x1.x*k;
		x1=dot(-1e9,-1e9*k+b);x2=dot(1e9,1e9*k+b);
		if (!flag)swap(x1,x2);
		return line(x1,x2);
	}
};
double chaji(dot x,dot y){
	return x.x*y.y-x.y*y.x;
}
double neiji(dot x,dot y){
	return x.x*y.x+x.y*y.y;
}
double cos(dot x,dot y){
	if (!x.len()||!y.len())return 0;
	return neiji(x,y)/x.len()/y.len();
}
dot Projection(dot x,line y){//求x关于直线y的投影点（垂足） 
	y.x2=y.x2-y.x1;
	x=x-y.x1;
	double len=cos(x,y.x2)*x.len()/y.x2.len();
	y.x2=y.x2*len;
	return y.x2+y.x1;
}
dot Reflection(dot x,line y){//求x关于直线y的对称点 
	dot z=Projection(x,y);
	return z*2-x;
}
int Counter_Clockwise(dot x,line y){//求两个向量的五种关系 
	x=x-y.x1;y.x2=y.x2-y.x1;
	if (chaji(y.x2,x)!=0){
		if (chaji(y.x2,x)>0)return 1;
		return 2;
	} 
	if (fabs(cos(x,y.x2)+1)<eps)return 3;
	if (x.len()>y.x2.len())return 4;
	return 5;
} 
int Parallel_Orthogonal(line x,line y){//求两个直线是垂直还是平行还是其他 
	dot a=x.getdot(),b=y.getdot();
	if (chaji(a,b)==0)return 2;
	if (neiji(a,b)==0)return 1;
	return 0;
}
int Intersection(line x,line y){//求两条线段是否相交 
	int Minx1=min(x.x1.x,x.x2.x),Maxx1=max(x.x1.x,x.x2.x);
	int Minx2=min(y.x1.x,y.x2.x),Maxx2=max(y.x1.x,y.x2.x);
	int Miny1=min(x.x1.y,x.x2.y),Maxy1=max(x.x1.y,x.x2.y);
	int Miny2=min(y.x1.y,y.x2.y),Maxy2=max(y.x1.y,y.x2.y);
	if (Minx1>Maxx2||Minx2>Maxx1)return 0;
	if (Miny1>Maxy2||Miny2>Maxy1)return 0;
	if (chaji(x.getdot(),y.x1-x.x1)*chaji(x.getdot(),y.x2-x.x1)>0)return 0;
	if (chaji(y.getdot(),x.x1-y.x1)*chaji(y.getdot(),x.x2-y.x1)>0)return 0;
	return 1;
}
int Intersection2(line x,line y){//求线段和直线是否相交 
	if (chaji(y.getdot(),x.x1-y.x1)*chaji(y.getdot(),x.x2-y.x1)>0)return 0;
	return 1;
}
dot CrossPoint(line x,line y){//求两条线段的交点 
	if (fabs(cos(x.getdot(),y.getdot())-1)<eps||fabs(cos(x.getdot(),y.getdot())+1)<eps){
		if (x.x1<x.x2)swap(x.x1,x.x2);
		if (y.x1<y.x2)swap(y.x1,y.x2);
		if (x.x2<y.x2)return y.x2;
		else return x.x2;
	}
	else {
		if (x.x2.x-x.x1.x==0){
			double k2=(y.x2.y-y.x1.y)/(y.x2.x-y.x1.x),b2=y.x2.y-y.x2.x*k2;
			return dot(x.x2.x,x.x2.x*k2+b2);
		}
		if (y.x2.x-y.x1.x==0){
			double k1=(x.x2.y-x.x1.y)/(x.x2.x-x.x1.x),b1=x.x2.y-x.x2.x*k1;
			return dot(y.x2.x,y.x2.x*k1+b1);			
		}
		double k1=(x.x2.y-x.x1.y)/(x.x2.x-x.x1.x),b1=x.x2.y-x.x2.x*k1;
		double k2=(y.x2.y-y.x1.y)/(y.x2.x-y.x1.x),b2=y.x2.y-y.x2.x*k2;
		dot ans;
		ans.x=(b2-b1)/(k1-k2);ans.y=ans.x*k1+b1;
		return ans;
	}
} 
double Dis(dot x,dot y){//点到点的距离 
	return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));
}
double dist(line x,dot y){//点到线段的距离 
	dot P=Projection(y,x);
	double k=neiji(x.getdot(),P-x.x1)/neiji(x.getdot(),x.getdot());
	if (k<=0)return Dis(x.x1,y);
	if (k>=1)return Dis(x.x2,y);
	return Dis(y,P);
}
double Distance(line x,line y){//线段之间距离 
	return min(min(dist(x,y.x1),dist(x,y.x2)),min(dist(y,x.x1),dist(y,x.x2)));
}
struct polygon{
	vector<dot > A;
	double S(){//多边形面积
		double ans=0;
		for (int i=0;i+1<A.size();i++)ans+=chaji(A[i],A[i+1])/2;
		if (A.size()>1)ans+=chaji(A[A.size()-1],A[0])/2;
		return ans;		
	}
	double C(){//多边形周长 
		double ans=0;
		for (int i=0;i+1<A.size();i++)ans+=Dis(A[i],A[i+1]);
		if (A.size()>1)ans+=Dis(A[A.size()-1],A[0]);
		return ans;
	}
	void read(){
		int n;scanf("%d",&n);A.resize(n);
		for (int i=0;i<n;i++)A[i].read();
	}
	int Is_Convex(){//是否是凸多边形 
		for (int i=0;i<A.size();i++)
			if (chaji(A[(i+1)%A.size()]-A[i],A[(i+2)%A.size()]-A[(i+1)%A.size()])<0)
				return 0;
		return 1;
	}
};
int PolygonPointContainment(polygon G,dot x){//射线和多边形的关系
	for (int i=0;i<G.A.size();i++)
		if (Counter_Clockwise(x,line(G.A[i],G.A[(i+1)%G.A.size()]))==5)return 1;
	for (int i=0;i<G.A.size();i++)
		if (x==G.A[i])return 1;
	double k=sqrt(2)+1,b=x.y-x.x*k;
	dot x2=dot(-1000000000,-1000000000*k+b);line R=line(x,x2);
	int ans=0;
	for (int i=0;i<G.A.size();i++)
		if (Intersection(R,line(G.A[i],G.A[(i+1)%G.A.size()])))ans++;
	if (ans&1)return 2;
	return 0;	
}
int isclock(dot x,dot y,dot z){//是否顺时针 
	return chaji(z-x,y-x)<0;
}
polygon Convex_Hull(polygon G){//求凸包 
	polygon ans1,ans2;
	sort(G.A.begin(),G.A.end());
	ans1.A.push_back(G.A[0]);ans1.A.push_back(G.A[1]);
	for (int i=2;i<G.A.size();i++){
		while (ans1.A.size()>=2&&isclock(ans1.A[ans1.A.size()-2],ans1.A[ans1.A.size()-1],G.A[i]))
			ans1.A.pop_back();
		ans1.A.push_back(G.A[i]);	
	}
	ans2.A.push_back(G.A[G.A.size()-1]);ans2.A.push_back(G.A[G.A.size()-2]);
	for (int i=G.A.size()-3;i>=0;i--){
		while (ans2.A.size()>=2&&isclock(ans2.A[ans2.A.size()-2],ans2.A[ans2.A.size()-1],G.A[i]))
			ans2.A.pop_back();
		ans2.A.push_back(G.A[i]);		
	}
	for (int i=1;i<ans2.A.size()-1;i++)ans1.A.push_back(ans2.A[i]);
	return ans1;
}
double DiameterofaConvexPolygon(polygon G){//求直径 
	int l=0,r=1,flag=1;
	double ans=Dis(G.A[0],G.A[1]);
	while (l!=0||flag){
		flag=0;
		while (Dis(G.A[l],G.A[r])<=Dis(G.A[l],G.A[(r+1)%G.A.size()])){
			r=(r+1)%G.A.size();
			ans=max(ans,Dis(G.A[l],G.A[r]));
		}
		l=(l+1)%G.A.size();
		ans=max(ans,Dis(G.A[l],G.A[r]));
	}
	return ans;
}
double Convex_Cut(polygon G,line x){//求多边形在线的左边的部分 
	polygon ans;line y=x;
	for (int i=0;i<G.A.size();i++){
		if (chaji(y.x2-y.x1,G.A[i]-y.x1)>=0)ans.A.push_back(G.A[i]);
		if (Intersection2(line(G.A[i],G.A[(i+1)%G.A.size()]),y))
			ans.A.push_back(CrossPoint(line(G.A[i],G.A[(i+1)%G.A.size()]),y));	
	}
	return ans.S();
}
int main(){
	polygon A;
	A.read();
	int T;
	scanf("%d",&T);
	while (T--){
		line x;
		x.read();
		printf("%.10lf\n",Convex_Cut(A,x));
	}
}