点击打开链接
题意：
给你一个10*10的方格， 然后在里面放不超过十堵墙。然后问你从 （0，5）->（10，5）的最短路。
题解：
最短路，但是建图非常恶心，需要判断线段之间是否相交。不相交才能建边。
判断两线段是否相交。模板
double mult(Point a, Point b, Point c) { return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y); } //aa, bb为一条线段两端点 cc, dd为另一条线段的两端点 相交返回true, 不相交返回false bool intersect(Point aa, Point bb, Point cc, Point dd) { if ( max(aa.x, bb.x)<min(cc.x, dd.x) ) { return false; } if ( max(aa.y, bb.y)<min(cc.y, dd.y) ) { return false; } if ( max(cc.x, dd.x)<min(aa.x, bb.x) ) { return false; } if ( max(cc.y, dd.y)<min(aa.y, bb.y) ) { return false; } if ( mult(cc, bb, aa)*mult(bb, dd, aa)<0 ) { return false; } if ( mult(aa, dd, cc)*mult(dd, bb, cc)<0 ) { return false; } return true; } 之后就是跑一边spfa。 #include <cstdio> #include <cstring> #include <iostream> #include <math.h> #include <queue> #include <map> using namespace std; #define inf 0x7ffffff map<pair<double,double>,int>m; pair<double ,double>p1,p2,a[155]; pair<pair<double,double>,pair<double,double> >wall[55]; int n,cnt,nn,cnt2; double mult(pair<double,double>a0,pair<double,double>a1,pair<double,double>a2){ return (a0.first-a2.first)*(a1.second-a2.second)-(a1.first-a2.first)*(a0.second-a2.second); } int judge(pair<double,double>a0,pair<double,double>a1,pair<double,double>a2,pair<double,double>a3){ if ( max(a0.first, a1.first)<=min(a2.first, a3.first) ) return false; if ( max(a0.second, a1.second)<=min(a2.second, a3.second) ) return false; if ( max(a2.first, a3.first)<=min(a0.first, a1.first) ) return false; if ( max(a2.second, a3.second)<=min(a0.second, a1.second) ) return false; if ( mult(a2, a1, a0)*mult(a1, a3, a0)<=0 ) return false; if ( mult(a0, a3, a2)*mult(a3, a1, a2)<=0 ) return false; return true; } struct Edge{ int v; double w; Edge(int _v=0,double _w=0):v(_v),w(_w){} }; double get_d(pair<double,double>x,pair<double,double>y){ return sqrt((x.first-y.first)*(x.first-y.first)+(x.second-y.second)*(x.second-y.second)); } vector<Edge>e[55*55]; void addedge(int u,int v,double w){ e[u].push_back(Edge(v,w)); } int vis[111]; double dis[111]; void spfa(){ memset(vis,0,sizeof(vis)); for(int i=1;i<=cnt;++i) dis[i]=inf; vis[1]=1; dis[1]=0; queue<int>que; while(!que.empty())que.pop(); que.push(1); while(!que.empty()){ int u=que.front(); que.pop(); vis[u]=0; for(int i=0;i<e[u].size();++i){ int v=e[u][i].v; if(dis[v]>dis[u]+e[u][i].w){ dis[v]=dis[u]+e[u][i].w; if(!vis[v]){ vis[v]=1; que.push(v); } } } } } int main(){ double b,mm; while(scanf("%d",&n)){ if(n==-1) break; for(int i=0;i<100;++i) e[i].clear(); cnt=0,nn=2,cnt2=0; a[++cnt].first=0,a[cnt].second=5;m[a[cnt]]=cnt; a[++cnt].first=10,a[cnt].second=5;m[a[cnt]]=cnt; int T=n; while(T--){ scanf("%lf",&mm); for(int i=1;i<=4;++i){ scanf("%lf",&b); a[++cnt].first=mm,a[cnt].second=b;m[a[cnt]]=cnt; } p1.first=mm,p1.second=0,p2.first=mm,p2.second=10; wall[++cnt2].first=p1,wall[cnt2].second=a[nn+1]; wall[++cnt2].first=a[nn+2],wall[cnt2].second=a[nn+3]; wall[++cnt2].first=a[nn+4],wall[cnt2].second=p2; nn=cnt; } for(int i=1;i<=cnt;++i){ for(int j=i+1;j<=cnt;++j){ int f=1; for(int k=1;k<=cnt2;++k) if(judge(a[i],a[j],wall[k].first,wall[k].second)){ f=0;break; } if(f){ double t=get_d(a[i],a[j]); addedge(m[a[i]],m[a[j]],t); addedge(m[a[j]],m[a[i]],t); } } } spfa(); printf("%.2f\n",dis[2]); } return 0; }