广东佛山哪家公司建网站,本地视频做成链接网址,腾讯3大外包公司,公司做网站费用和人员配备SPFA。 我们关键是要找到关键点#xff0c;包括起点#xff0c;终点#xff0c;和相邻矩形接触线段的上端点和下端点#xff08;如图有红色圈住的点为关键点#xff09;。 我们要做的就是在这些关键点之间连边。 我们把这些关键的点拿出来: 其实就是一些竖直的线段。 除了…SPFA。 我们关键是要找到关键点包括起点终点和相邻矩形接触线段的上端点和下端点如图有红色圈住的点为关键点。 我们要做的就是在这些关键点之间连边。 我们把这些关键的点拿出来: 其实就是一些竖直的线段。 除了S和T外从左到右或者从右到左穿过线段所在的直线必须在线段中穿过去也就是说有个上边界和下边界。 如图是S到第4条竖直的线段的上边界l1和下边界l2。 我们先按X坐标从小到大排序枚举边的起点向左或者向右连边如果遇到竖直的线段用叉积更改上下边界即可。 构好图就直接SPFA即可。 #includecstdio
#includecmath
#includealgorithm
#includecstringusing namespace std;const int maxN2000;
const double INF1e15;
const double EPS1e-9;inline int dblcmp(double x){if (abs(x)EPS)return 0;return x0?1:-1;}
inline double sqr(double x){return x*x;}struct Tpoint{double x,y;inline Tpoint(){}inline Tpoint(double _x,double _y){x_x;y_y;}};inline double dis(Tpoint a,Tpoint b){return sqrt(sqr(a.x-b.x)sqr(a.y-b.y));}
inline double det(Tpoint p0,Tpoint p1,Tpoint p2){return (p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x);}int N;
Tpoint square[maxN100][2];
Tpoint a[maxN100][2];
int id[maxN100][2],cnt;
int now,info[2*maxN100];
struct Tedge{int v,next;double dis;}edge[2*maxN*2*maxN1000];
double ans,v;
Tpoint S,T;
int eS,eT,idS,idT;inline void addedge(int u,int v,double dis){now;edge[now].vv;edge[now].disabs(dis);edge[now].nextinfo[u];info[u]now;}inline void solve(Tpoint s,int num,int l){if (num!idS num!idT num%20){addedge(num,num1,dis(a[l][0],a[l][1]));addedge(num1,num,dis(a[l][0],a[l][1]));}Tpoint low,high,t1,t2;bool flag0;for(int il-1;i1;i--){if (!flag (id[i][0]idS || id[i][0]idT)){addedge(num,id[i][0],dis(s,a[i][0]));addedge(id[i][0],num,dis(s,a[i][0]));continue;}if (!flag){addedge(num,id[i][0],dis(s,a[i][0]));addedge(id[i][0],num,dis(s,a[i][0]));addedge(num,id[i][1],dis(s,a[i][1]));addedge(id[i][1],num,dis(s,a[i][1]));lowa[i][0];higha[i][1];flag1;continue;}t1a[i][0];t2a[i][1];if ( dblcmp(det(s,low,t1))0 dblcmp(det(s,high,t1))0 ){addedge(num,id[i][0],dis(s,a[i][0]));addedge(id[i][0],num,dis(s,a[i][0]));}if ( dblcmp(det(s,low,t2))0 dblcmp(det(s,high,t2))0 ){addedge(num,id[i][1],dis(s,a[i][1]));addedge(id[i][1],num,dis(s,a[i][1]));}if (id[i][0]!idS id[i][0]!idT){if ( dblcmp( det(s,low,t2) ) 1 ) break;if ( dblcmp( det(s,high,t1)) -1 ) break;if ( dblcmp( det(s,low,t1) ) -1 ) lowt1;if ( dblcmp( det(s,high,t2)) 1 ) hight2;}}}int head,tail,queue[7*2*maxN100];
bool vis[2*maxN100];
double f[2*maxN100];
inline double SPFA(){int SidS,TidT;for(int i1;icnt;i) f[i]INF;queue[headtail0]S;f[S]0.0;vis[S]1;while(headtail){int uqueue[(head)%(7*2*maxN100)],v,i;double dis;vis[u]0;for(iinfo[u],vedge[i].v,disedge[i].dis;i!-1;iedge[i].next,vedge[i].v,disedge[i].dis)if ( dblcmp(disf[u]-f[v])-1 ){f[v]disf[u];if (!vis[v]){vis[v]1;queue[(tail)%(7*2*maxN100)]v;if ( dblcmp(f[queue[head%(7*2*maxN100)]]-f[queue[tail%(7*2*maxN100)]])1 ) swap(queue[tail%(7*2*maxN100)],queue[head%(7*2*maxN100)]);}}}return abs(f[T]);}int main(){freopen(car.in,r,stdin);freopen(car.out,w,stdout);scanf(%d\n,N);for(int i1;iN;i)scanf(%lf%lf%lf%lf\n,square[i][0].x,square[i][0].y,square[i][1].x,square[i][1].y);scanf(%lf%lf\n,S.x,S.y);for(int i1;iN;i)if (dblcmp(square[i][0].x-S.x)0 dblcmp(S.x-square[i][1].x)0 dblcmp(square[i][0].y-S.y)0 dblcmp(S.y-square[i][1].y)0){eSi;break;}scanf(%lf%lf\n,T.x,T.y);for(int i1;iN;i)if (dblcmp(square[i][0].x-T.x)0 dblcmp(T.x-square[i][1].x)0 dblcmp(square[i][0].y-T.y)0 dblcmp(T.y-square[i][1].y)0){eTi;break;}int gN;N0;for(int i1;ig;i){if (ieS){N;a[N][0].xS.x;a[N][0].yS.y;a[N][1].xS.x;a[N][1].yS.y;idSid[N][0]id[N][1]cnt;}if (ieT){N;a[N][0].xT.x;a[N][0].yT.y;a[N][1].xT.x;a[N][1].yT.y;idTid[N][0]id[N][1]cnt;}if (ig) continue;N;a[N][0].xsquare[i][1].x;a[N][0].ymax(square[i][0].y,square[i1][0].y);a[N][1].xsquare[i][1].x;a[N][1].ymin(square[i][1].y,square[i1][1].y);id[N][0]cnt;id[N][1]cnt;}memset(info,-1,sizeof(info));now-1;for(int i2;iN;i)for(int j0;j2;j)solve(a[i][j],id[i][j],i);ansSPFA();scanf(%lf\n,v);ansans/v;printf(%0.10lf\n,ans);return 0;} View Code 转载于:https://www.cnblogs.com/maijing/p/4698959.html
