#include #include #include #include #include #include #include using namespace std; const int NODE = 300 * 300 + 10; typedef struct {int t;double cost;}Edge; vector edge[NODE]; bool ben[NODE]; const double eps = 1e-10; typedef complex P; typedef pair Line; namespace std{ bool operator==(const P &a,const P & b){ if (abs(a.real()-b.real()) < 1e-10 && abs(a.imag()-b.imag()) 1e-10)return a.real() < b.real(); return a.imag() < b.imag(); } }; double cross(P a,P b){ return ( a.real()*b.imag() - a.imag()*b.real()); } bool is_point_online(P a,P b,P c){ return ( abs(a-c)+abs(b-c) < abs(a-b)+eps); } bool is_intersected_ls(P a1,P a2,P b1,P b2){ if ( is_point_online(a1,a2,b1))return true; if ( is_point_online(a1,a2,b2))return true; if ( is_point_online(b1,b2,a1))return true; if ( is_point_online(b1,b2,a2))return true; if ( ( cross(a2-a1,b1-a1) * cross(a2-a1,b2-a1) makegraph(vector &in,vector

& stop,P &s,P &t,int &n){ vector

a=stop; a.push_back(s); a.push_back(t); for(int i=0;i<(int)in.size();i++){ a.push_back(in[i].first); a.push_back(in[i].second); for(int j=i+1;j<(int)in.size();j++){ if (is_intersected_ls(in[i].first,in[i].second,in[j].first,in[j].second)){ a.push_back(intersection_ls(in[i].first,in[i].second,in[j].first,in[j].second)); } } } sort(a.begin(),a.end()); a.erase(unique(a.begin(),a.end()),a.end()); /* for(int i=0;i > cand; for(int j=0;j<(int)a.size();j++){ if (is_point_online(in[i].first,in[i].second,a[j]))cand.push_back(make_pair(a[j],j)); } sort(cand.begin(),cand.end()); /* for(int j=0;j ret; for(int i=0;i<(int)a.size();i++){ if (abs(s-a[i]) < eps)ret.first = i; if (abs(t-a[i]) < eps)ret.second = i; } for(int i=0;i<(int)stop.size();i++){ for(int j=0;j<(int)a.size();j++){ if (abs(stop[i]-a[j]) < eps)ben[j] = true; } } return ret; } bool neighbor[NODE]; bool vis[NODE]; set > S; void dfs(int now,double &a){ if (vis[now])return; vis[now] = true; if (ben[now])return; for(int i=0;i<(int)edge[now].size();i++){ int next =edge[now][i].t; double cost = edge[now][i].cost; int ta=now,tb=next; if (ta > tb)swap(ta,tb); if (S.count(make_pair(ta,tb)) == 0){ a += cost,S.insert(make_pair(ta,tb)); } dfs(next,a); } } double bfs(int s){ queue Q; double ret = 0; Q.push(s); vis[s] = true; while(!Q.empty()){ int now = Q.front();Q.pop(); for(int i=0;i<(int)edge[now].size();i++){ int next = edge[now][i].t; int ta = now,tb = next; if (ta > tb)swap(ta,tb); if (S.count(make_pair(ta,tb)) == 0){ ret += edge[now][i].cost; S.insert(make_pair(ta,tb)); } if (vis[next] || neighbor[next])continue; if (!vis[next] && !neighbor[next]){ Q.push(next); vis[next] = true; } } } return ret; } double solve(int n,int s,int t,double sum){ double ta = 0; S.clear(); for(int i=0;i next)continue; if (S.count(make_pair(now,next)) == 0){ tmp -= edge[i][j].cost; } } } return sum - tmp; } int main(){ int n,m; while(cin>>n>>m && n){ P s,t; double sum = 0; for(int i=0;i in(n); vector

stop(m); for(int i=0;i>in[i].first.real()>>in[i].first.imag(); cin>>in[i].second.real()>>in[i].second.imag(); sum += abs(in[i].first-in[i].second); } for(int j=0;j>stop[j].real()>>stop[j].imag(); } cin>>s.real()>>s.imag(); cin>>t.real()>>t.imag(); int node; pair tmp = makegraph(in,stop,s,t,node); /* for(int i=0;i