吉林省建设集团有限公司网站,软件设计师中级考什么,wordpress广告位的添加方法,ui外包网站题意#xff1a;在一个矩形平面内#xff0c;有若干道墙#xff0c;现求从左部某一点到右部某一点的最短路径。 解法#xff1a;有一个事实是线路一定是从门两边的点上通过的#xff0c;不可能出现从中间穿过的可能。因此我们就枚举两两点之间是否可达#xff0c;这里就要…题意在一个矩形平面内有若干道墙现求从左部某一点到右部某一点的最短路径。 解法有一个事实是线路一定是从门两边的点上通过的不可能出现从中间穿过的可能。因此我们就枚举两两点之间是否可达这里就要使用到线段相交的判定。构好图之后就是一个spfa搞定。 代码如下 #include iostream
#include cstdio
#include algorithm
#include cmath
#include cstring
using namespace std;int N;struct Wall {double x, a, b, c, d;
}w[20];struct Point {double x, y;
}e[105];
int idx;struct Line {Point a, b;Line(Point x, Point y) {a x, b y;}friend bool cross(const Line , const Line );
};double G[105][105];bool cross(const Line Line1, const Line Line2) {double Xa1 Line1.a.x;double Ya1 Line1.a.y;double Xa2 Line1.b.x;double Ya2 Line1.b.y;double Xb1 Line2.a.x;double Yb1 Line2.a.y;double Xb2 Line2.b.x;double Yb2 Line2.b.y;if(((Xa2-Xa1)*(Yb1-Ya1)-(Xb1-Xa1)*(Ya2-Ya1))*((Xa2-Xa1)*(Yb2-Ya1)-(Xb2-Xa1)*(Ya2-Ya1))0)return false;if(((Xb2-Xb1)*(Ya1-Yb1)-(Xa1-Xb1)*(Yb2-Yb1))*((Xb2-Xb1)*(Ya2-Yb1)-(Xa2-Xb1)*(Yb2-Yb1))0)return false;return true;
}void insert(double x, double y) {e[idx].x x, e[idx].y y;idx;
}bool legal(int x, int y) {Line line Line(e[x], e[y]);int l (x-1)/4, r (y-1)/4; // 分别计算出这些点属于哪一面墙再枚举中间的墙if (x 0) l -1; // x0时需特殊处理for (int i l1; i r; i) { // 计算是否被墙挡住if (!cross(line, Line(e[i*41], e[i*42])) // 如果不从中间墙的某道门穿过的话 !cross(line, Line(e[i*43], e[i*44]))) {return false;}}return true;
}double dist(const Point a, const Point b) {return sqrt((a.x - b.x) * (a.x - b.x) (a.y - b.y) * (a.y - b.y));
}void build() {for (int i 0; i idx; i) {for (int j i 1; j idx; j) { // 枚举所有的两两组合 if (legal(i, j)) {G[i][j] dist(e[i], e[j]);}}}
}#include queue
bool vis[105];
double dis[105];
void spfa() {memset(vis, 0, sizeof (vis));for (int i 0; i idx; i) {dis[i] 10000000; }dis[0] 0;queueintq;q.push(0);vis[0] true;while (!q.empty()) {int v q.front();q.pop(); vis[v] false;for (int i v1; i idx; i) {if (G[v][i] ! 10000000 dis[i] dis[v] G[v][i]) {dis[i] dis[v] G[v][i];if (!vis[i]) {vis[i] true; q.push(i);}}} }
}int main() {while (scanf(%d, N), N ! -1) {for (int i 0; i 105; i) {for (int j 0; j 105; j) {G[i][j] 10000000; }}idx 0;insert(0.0, 5.0);for (int i 0; i N; i) {scanf(%lf %lf %lf %lf %lf, w[i].x, w[i].a, w[i].b, w[i].c, w[i].d);insert(w[i].x, w[i].a), insert(w[i].x, w[i].b);insert(w[i].x, w[i].c), insert(w[i].x, w[i].d);// 读取所有的墙并且添加四个点}insert(10, 5);build();spfa();printf(%.2f\n, dis[idx-1]);}return 0;
}
