text: resize(nv); for(int j=0; j<nv; j++){ int x,y; cin >> x >> y; poly[i][j] = P(x, y); } } vector<L> lines(m); for(int i=0; i<m; i++){ int xs,ys,xt,yt; cin >> xs >> ys >> xt >> yt; lines[i] = L(P(xs, ys), P(xt, yt)); } double th,phi; cin >> th >> phi; th *= PI/180; phi *= PI/180; P dir = P(cos(th+PI), sin(th+PI)) /tan(phi); for(int i=0; i<n; i++){ VP tmp = poly[i]; P idir = dir *h[i]; for(int j=0; j<(int)poly[i].size(); j++){ tmp.push_back(poly[i][j] +idir); } poly[i] = convex(tmp); } VP sg(2); int sx,sy,tx,ty; cin >> sx >> sy >> tx >> ty; sg[0] = P(sx, sy); sg[1] = P(tx, ty); //calc costs of edges auto ret = arrangementEX(lines, sg); auto &adj = ret.first; VP &plist = ret.second; int pn = plist.size(); int sidx = lower_bound(plist.begin(), plist.end(), sg[0]) -plist.begin(); int gidx = lower_bound(plist.begin(), plist.end(), sg[1]) -plist.begin(); for(int i=0; i<pn; i++){ for(int j=i+1;j<pn; j++){ if(adj[i][j] == INF) continue; L e(plist[i], plist[j]); VP cp(2); cp[0] = e[0]; cp[1] = e[1]; for(int k=0; k<n; k++){ int vn = poly[k].size(); for(int l=0; l<vn; l++){ L edge(poly[k][l], poly[k][(l+1)%vn]); if(!isParallel(e, edge) && intersectSS(e, edge)){ cp.push_back(crosspointLL(e, edge)); } } } sort(cp.begin(), cp.end()); cp.erase(unique(cp.begin(), cp.end()), cp.end()); double cost = 0; for(int k=0; k<(int)cp.size()-1; k++){ P mid = (cp[k] +cp[k+1]) /2.0; bool in = false; for(int l=0; l<n; l++){ if(in_poly(mid, poly[l]) >= 0){ in = true; break; } } if(!in){ cost += abs(cp[k+1] -cp[k]); } } adj[i][j] = adj[j][i] = cost; } } for(int k=0; k<pn; k++){ for(int i=0; i<pn; i++){ for(int j=0; j<pn; j++){ adj[i][j] = min(adj[i][j], adj[i][k] +adj[k][j]); } } } cout << fixed << setprecision(4); cout << adj[sidx][gidx] << endl; } return 0; }