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

浅浅的花香味﹌ 2022-07-12 10:14 470阅读 0赞

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

\#include <iostream> \#include <cmath> 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<mce:script type="text/javascript" src="http://hi.images.csdn.net/js/blog/tiny\_mce/themes/advanced/langs/zh.js" mce\_src="http://hi.images.csdn.net/js/blog/tiny\_mce/themes/advanced/langs/zh.js"></mce:script><mce:script type="text/javascript" src="http://hi.images.csdn.net/js/blog/tiny\_mce/plugins/syntaxhl/langs/zh.js" mce\_src="http://hi.images.csdn.net/js/blog/tiny\_mce/plugins/syntaxhl/langs/zh.js"></mce:script>; 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; \}