Problem: In the International City of Pipe Construction, it is planned to repair the water pipe at a certain point in the water pipe network. The network consists of water pipe segments, stop valves and source point. A water pipe is represented by a segment on a 2D-plane and intersected pair of water pipe segments are connected at the intersection point. A stop valve, which prevents from water flowing into the repairing point while repairing, is represented by a point on some water pipe segment. In the network, just one source point exists and water is supplied to the network from this point.

Of course, while repairing, we have to stop water supply in some areas, but, in order to reduce the risk of riots, the length of water pipes stopping water supply must be minimized. What you have to do is to write a program to minimize the length of water pipes needed to stop water supply when the coordinates of end points of water pipe segments, stop valves, source point and repairing point are given.



Input

A data set has the following format:

> N M
>  xs1 ys1 xd1 yd1
>  ...
>  xsN ysN xdN ydN
>  xv1 yv1
>  ...
>  xvM yvM
>  xb yb
>  xc yc
>

The first line of the input contains two integers, N (1 ≤ N ≤ 300) and M (0 ≤ M ≤ 1,000) that indicate the number of water pipe segments and stop valves. The following N lines describe the end points of water pipe segments. The i-th line contains four integers, xsi, ysi, xdi and ydi that indicate the pair of coordinates of end points of i-th water pipe segment. The following M lines describe the points of stop valves. The i-th line contains two integers, xvi and yvi that indicate the coordinate of end points of i-th stop valve. The following line contains two integers, xb and yb that indicate the coordinate of the source point. The last line contains two integers, xc and yc that indicate the coordinate of the repairing point.

You may assume that any absolute values of coordinate integers are less than 1,000 (inclusive.) You may also assume each of the stop valves, the source point and the repairing point is always on one of water pipe segments and that that each pair among the stop valves, the source point and the repairing point are different. And, there is not more than one intersection between each pair of water pipe segments. Finally, the water pipe network is connected, that is, all the water pipes are received water supply initially.

Output

Print the minimal length of water pipes needed to stop water supply in a line. The absolute or relative error should be less than or 10-6. When you cannot stop water supply to the repairing point even though you close all stop valves, print "`-1`" in a line.

Examples

Input

1 2
0 0 10 0
1 0
9 0
0 0
5 0


Output

9.0


Input

5 3
0 4 2 4
0 2 2 2
0 0 2 0
0 0 0 4
2 0 2 4
0 2
1 0
2 2
1 4
2 1


Output

3.0


Input

2 1
0 0 0 4
0 2 2 2
1 2
0 1
0 3


Output

-1

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


//#define EPS 0.0000001
#define NUM 305

struct Point{
	Point(double arg_x,double arg_y){
		x = arg_x;
		y = arg_y;
	}

	Point(){
		x = y = 0.0;
	}

	Point operator + (Point p){ return Point(x+p.x,y+p.y); }
	Point operator - (Point p){ return Point(x-p.x,y-p.y);}
	Point operator * (double a){ return Point(a*x,a*y); }
	Point operator / (double a){ return Point(x/a,y/a); }

	double abs(){ return sqrt(norm()); }
	double norm(){ return x*x + y*y; }

	bool operator<(const Point &p) const{
		return fabs(x-p.x) > EPS? x < p.x: y < p.y;
	}

	bool operator == (const Point &p) const{
		return fabs(x-p.x) < EPS && fabs(y-p.y) < EPS;
	}

	double x,y;
};
typedef Point Vector;

struct Line{
public:
	Point p[2];
	Line(Point p1,Point p2){
		p[0] = p1;
		p[1] = p2;
	}
	Line(){
	}
};

struct Info{
	Info(Point arg_cross_point,int arg_index){

		cross_point.x = arg_cross_point.x;
		cross_point.y = arg_cross_point.y;
		index = arg_index;
	}
	bool operator<(const struct Info &arg) const{
		return cross_point < arg.cross_point;
	}
	bool operator==(const struct Info &arg) const{
		return cross_point == arg.cross_point;
	}

	Point cross_point;
	int index;
};

struct Edge{
	Edge(int arg_to, double arg_cost){

		to = arg_to;
		cost = arg_cost;
	}
	int to;
	double cost;
};

int N,M;
int num_nodes;
int start_index = -1,repair_index = -1;
vector<Info> on_segment[NUM];
vector<Point> NODES,STOP_VALVE;
Point start,goal;
Line water_pipe[NUM];
vector<Edge> G[NUM*NUM];
map<int,bool> IS_STOP;
map<pair<int,int>,bool> MAP;
map<pair<int,int>,bool> USED;


//交点を求める関数
Point calc_Cross_Point(double x1,double x2,double x3,double x4,double y1,double y2,double y3,double y4){
	Point ret;
	ret.x = ((x2-x1)*(y3*(x4-x3)+x3*(y3-y4))-(x4-x3)*(y1*(x2-x1)+x1*(y1-y2)))/((y2-y1)*(x4-x3)-(y4-y3)*(x2-x1));
	if(x1 != x2){
		ret.y = ((y2-y1)*ret.x+y1*(x2-x1)+x1*(y1-y2))/(x2-x1);
	}else{
		ret.y = ((y4-y3)*ret.x+y3*(x4-x3)+x3*(y3-y4))/(x4-x3);
	}
	return ret;
}

//インタフェース関数
Point calc_Cross_Point(Point a,Point b,Point c,Point d){
	return calc_Cross_Point(a.x,b.x,c.x,d.x,a.y,b.y,c.y,d.y);
}

Point calc_Cross_Point(Line A,Line B){

	return calc_Cross_Point(A.p[0],A.p[1],B.p[0],B.p[1]);
}


int func(double x1,double y1,double x2, double y2, double xp, double yp){
	double naiseki,norm1,norm2,gaiseki;
	norm1 = sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
	norm2 = sqrt((xp-x1)*(xp-x1)+(yp-y1)*(yp-y1));
	naiseki = (xp-x1)*(x2-x1)+(yp-y1)*(y2-y1);
	gaiseki = (x2-x1)*(yp-y1)-(xp-x1)*(y2-y1);
	if(gaiseki > EPS){
		return 1;
	}else if(gaiseki < -EPS){
		return -1;
	}
	if(naiseki < -EPS){
		return 2;
	}

	if(norm1 < norm2){
		return -2;
	}
	return 0;
}


//★★直線ではなく、線分の交差判定★★
bool is_Cross(Line a,Line b){

	if(func(a.p[0].x,a.p[0].y,a.p[1].x,a.p[1].y,b.p[0].x,b.p[0].y)*
			func(a.p[0].x,a.p[0].y,a.p[1].x,a.p[1].y,b.p[1].x,b.p[1].y) <= 0 &&
			func(b.p[0].x,b.p[0].y,b.p[1].x,b.p[1].y,a.p[0].x,a.p[0].y)*
			func(b.p[0].x,b.p[0].y,b.p[1].x,b.p[1].y,a.p[1].x,a.p[1].y) <= 0){
		return true;
	}
	return false;
}

double calc_dist(Point A,Point B){

	return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}

Point calc_minus(Point a,Point b){
    Point ret;

    ret.x = a.x-b.x;
    ret.y = a.y-b.y;

    return ret;
}

double calc_len(Vector a){
    return sqrt(a.x*a.x+a.y*a.y);
}

double cross(Vector a,Vector b){
    return a.x*b.y-a.y*b.x;
}

double calc_slope(Line A){

	if(fabs(A.p[0].x-A.p[1].x) < EPS){

		return DBL_MAX;

	}else if(fabs(A.p[0].y-A.p[1].y) < EPS){

		return 0;

	}else{

		return (A.p[0].y-A.p[1].y)/(A.p[0].x-A.p[1].x);
	}
}

double norm(Vector a){
	return a.x*a.x+a.y*a.y;
}

double abs(Vector a){
	return sqrt(norm(a));
}

double dot(Vector a,Vector b){
    return a.x*b.x + a.y*b.y;
}


double getDistanceLP(Line l,Point p){
    return fabs(cross(calc_minus(l.p[1],l.p[0]),calc_minus(p,l.p[0]))/calc_len(calc_minus(l.p[1],l.p[0])));
}

//★★点と線分の距離★★
double getDistanceSP(Line l,Point p){
	if(dot(l.p[1]-l.p[0],p-l.p[0]) < 0.0) return abs(p-l.p[0]);
	if(dot(l.p[0]-l.p[1],p-l.p[1]) < 0.0) return abs(p-l.p[1]);
	return getDistanceLP(l,p);
}

int main(){


	scanf("%d %d",&N,&M);

	num_nodes = 0;

	int x1,y1,x2,y2;

	for(int i = 0; i < N; i++){

		scanf("%d %d %d %d",&x1,&y1,&x2,&y2);

		water_pipe[i].p[0].x = x1;
		water_pipe[i].p[0].y = y1;
		water_pipe[i].p[1].x = x2;
		water_pipe[i].p[1].y = y2;

		auto at = MAP.find(make_pair(x1,y1));
		if(at == MAP.end()){
			NODES.push_back(Point(water_pipe[i].p[0]));
			MAP[make_pair(x1,y1)] = true;
		}

		at = MAP.find(make_pair(x2,y2));
		if(at == MAP.end()){
			NODES.push_back(Point(water_pipe[i].p[1]));
			MAP[make_pair(x2,y2)] = true;
		}

		NODES.push_back(Point(water_pipe[i].p[1]));
	}


	int x,y;

	//止水バルブの取得

	for(int i = 0; i < M; i++){

		scanf("%d %d",&x,&y);

		STOP_VALVE.push_back(Point(x,y));

		NODES.push_back(Point(x,y));

	}

	int start_x,start_y;

	scanf("%d %d",&start_x,&start_y);
	NODES.push_back(Point(start_x,start_y));


	int repair_x,repair_y;

	scanf("%d %d",&repair_x,&repair_y);
	NODES.push_back(Point(repair_x,repair_y));

	//パイプとパイプの交点ノードの座標を求める

	for(int i = 0; i < N-1; i++){
		for(int k = i+1; k < N; k++){
			if(!is_Cross(water_pipe[i],water_pipe[k]))continue;

			if(water_pipe[i].p[0] == water_pipe[k].p[0] || water_pipe[i].p[0] == water_pipe[k].p[1] || //計算不要なのでSKIP
					water_pipe[i].p[1] == water_pipe[k].p[0] || water_pipe[i].p[1] == water_pipe[k].p[1])continue;

			Point tmp_point = calc_Cross_Point(water_pipe[i],water_pipe[k]);

			bool FLG = false;
			for(int a = 0; a < NODES.size(); a++){

				if(NODES[a] == tmp_point){
					FLG = true;
					break;
				}
			}

			if(FLG)continue;

			NODES.push_back(tmp_point);

		}
	}

	sort(NODES.begin(),NODES.end());
	NODES.erase(unique(NODES.begin(),NODES.end()),NODES.end());

	//線分と接触しているノードを線分に所属させる
	for(int i = 0; i < N; i++){
		for(int k = 0; k < NODES.size(); k++){
			if(NODES[k] == water_pipe[i].p[0] || NODES[k] == water_pipe[i].p[1]){ //計算するとnanになる
				on_segment[i].push_back(Info(NODES[k],k));
				continue;
			}

			if(getDistanceSP(water_pipe[i],NODES[k]) > EPS)continue;

			on_segment[i].push_back(Info(NODES[k],k));
		}
	}

	//止水バルブのインデックスを求める
	for(int i = 0; i < STOP_VALVE.size(); i++){

		for(int k = 0; k < NODES.size(); k++){
			if(NODES[k] == STOP_VALVE[i]){
				IS_STOP[k] = true;
				break;
			}

		}
	}


	//スタートノードのインデックスを求める
	Point start_point = Point(start_x,start_y);

	for(int k = 0; k < NODES.size(); k++){
		if(NODES[k] == start_point){
			start_index = k;
			break;
		}
	}

	//修理ポイントのインデックスを求める
	Point repair_point = Point(repair_x,repair_y);

	for(int k = 0; k < NODES.size(); k++){
		if(NODES[k] == repair_point){
			repair_index = k;
			break;
		}
	}

	double total_length = 0;

	//グラフを作成
	for(int i = 0; i < N; i++){

		sort(on_segment[i].begin(),on_segment[i].end());
		on_segment[i].erase(unique(on_segment[i].begin(),on_segment[i].end()),on_segment[i].end());

		for(int k = 1; k < on_segment[i].size(); k++){

			int from = on_segment[i][k-1].index;
			int to = on_segment[i][k].index;

			double tmp_dist = calc_dist(on_segment[i][k-1].cross_point,on_segment[i][k].cross_point);

			total_length += tmp_dist;

			G[from].push_back(Edge(to,tmp_dist));
			G[to].push_back(Edge(from,tmp_dist));
		}
	}

	double must_stop = 0;

	//修理ポイントから、止水バルブを通らずに行ける範囲の距離を求める[★必ず止める★]
	queue<int> Q;
	Q.push(repair_index);

	while(!Q.empty()){

		int tmp_node = Q.front();
		Q.pop();

		auto at = IS_STOP.find(tmp_node);

		if(at != IS_STOP.end()){ //tmp_nodeは止水バルブ

			continue;
		}

		for(int i = 0; i < G[tmp_node].size(); i++){

			int next_node = G[tmp_node][i].to;

			auto at = USED.find(make_pair(tmp_node,next_node));

			if(at != USED.end())continue; //エッジを通過済み

			if(next_node == start_index){

				printf("-1\n"); //水源から修理点までの間に止水バルブがないので不可
				return 0;
			}

			USED[make_pair(tmp_node,next_node)] = true;
			USED[make_pair(next_node,tmp_node)] = true;

			must_stop += G[tmp_node][i].cost;

			Q.push(next_node);
		}
	}

	//水源から、水を停めた範囲を通らずに、水を供給できる範囲を求める
	double can_supply = 0;

	Q.push(start_index);

	while(!Q.empty()){

		int tmp_node = Q.front();
		Q.pop();

		for(int i = 0; i < G[tmp_node].size(); i++){

			int next_node = G[tmp_node][i].to;

			auto at = USED.find(make_pair(tmp_node,next_node));
			if(at != USED.end())continue; //エッジを通過済み

			can_supply += G[tmp_node][i].cost;

			USED[make_pair(tmp_node,next_node)] = true;
			USED[make_pair(next_node,tmp_node)] = true;

			Q.push(next_node);
		}
	}
	printf("%.10lf\n",total_length-can_supply);

	return 0;
}