pku 1556 The Doors 计算几何之叉积判断线段是否相交-蒲公英云

pku 1556 The Doors 计算几何之叉积判断线段是否相交

这是黑书上的一道题目, 以前很少刷计算几何的题, 算是一个开端吧.

#include #include using namespace std; #define EPS 1e-8 #define INF 100000000 struct Wall { double x; double y[6]; }wall[20]; double dis[80][80]; double det(double x0, double y0, double x1, double y1, double x2, double y2) { return ((x1-x0)*(y2-y0) - (y1-y0)*(x2-x0)); } int dblcmp(double a) { if(fabs(a) < EPS) return 0; return a > 0?1:-1; } bool cross(double x0, double y0, double x1, double y1, double x2, double y2, double x3, double y3) { return (dblcmp(det(x0, y0, x1, y1, x3, y3)) ^ dblcmp(det(x0, y0, x1, y1, x2, y2))) == -2 && (dblcmp(det(x2, y2, x3, y3, x0, y0)) ^ dblcmp(det(x2, y2, x3, y3, x1, y1))) == -2; } bool direct(int i, int j, int p, int q) //wall i point j to wall p point q { int m, n; for(m = i+1; m < p; ++m) for(n = 0; n < 6; n += 2) if(cross(wall[i].x, wall[i].y[j], wall[p].x, wall[p].y[q], wall[m].x, wall[m].y[n], wall[m].x, wall[m].y[n+1])) return false; return true; } inline double dist(double x0, double y0, double x1, double y1) { return sqrt((x1-x0)*(x1-x0)+(y1-y0)*(y1-y0)); } double dijkstra(int n) { double min_dis[80]; bool s[80] = {0}; s[0] = true; for(int i = 0; i <= n; ++i) min_dis[i] = dis[0][i]; for(int i = 1; i <= n; ++i) { int min = INF; int index = 0; for(int j = 0; j <= n; ++j) if(!s[j] && min_dis[j] < min) { min = min_dis[j]; index = j; } s[index] = true; for(int j = 0; j <= n; ++j) if(!s[j] && min_dis[index] + dis[index][j] < min_dis[j]) min_dis[j] = min_dis[index] + dis[index][j]; } return min_dis[n]; } int main() { int n; while(scanf(“%d”, &n) && n != -1) { for(int i = 0; i < 4*n+2; ++i) for(int j = 0; j < 4*n+2; ++j) dis[i][j] = INF; int con = true; for(int i = 1; i <= n; ++i) { wall[i].y[0] = 0; wall[i].y[5] = 10; scanf(“%lf%lf%lf%lf%lf”, &wall[i].x, &wall[i].y[1], &wall[i].y[2], &wall[i].y[3], &wall[i].y[4]); if(wall[i].y[1] > 5 || wall[i].y[2] < 5&& wall[i].y[3] > 5 || wall[i].y[4] < 5) con = false; } wall[0].x = 0, wall[0].y[0] = 5; wall[n+1].x = 10, wall[n+1].y[0] = 5; if(con) { puts(“10.00”); continue; } for(int i = 1; i <= n; ++i) for(int j = 1; j <= 4; ++j) { if(i < n) { for(int k = 1; k <= 4; ++k) dis[(i-1)*4+j][i*4+k] = dist(wall[i].x, wall[i].y[j], wall[i+1].x, wall[i+1].y[k]); } if(direct(0, 0, i, j)) dis[0][4*(i-1)+j] = dist(0, 5, wall[i].x, wall[i].y[j]); if(direct(i, j, n+1, 0)) dis[4*(i-1)+j][4*n+1] = dist(wall[i].x, wall[i].y[j], 10, 5); for(int k = i+2; k <= n; ++k) for(int l = 1; l <= 4; ++l) if(direct(i, j, k, l)) dis[4*(i-1)+j][4*(k-1)+l] = dist(wall[i].x, wall[i].y[j], wall[k].x, wall[k].y[l]); } printf(“%.2lf/n”, dijkstra(4*n+1)); } return 0; }