计算几何:线段相交（迷宫寻宝）

计算几何:线段相交（迷宫寻宝）

计算几何:线段相交（迷宫寻宝） Time Limit(Common/Java):1000MS/3000MS          Memory Limit:65536KByte Description          一个叫ACM的寻宝者找到了一个藏宝图，它根据藏宝图找到了一个迷宫，这是一个很特别的迷宫，迷宫是一100*100的个正方形区域，里面有很多墙，这些墙都是由一些直线构成的，如下图。

墙把迷宫分隔成很多藏宝室，任何两个藏宝室之间都没有门。

ACM现在准备用开凿设备在相邻两个藏宝室的墙中间凿开一个门，最终取出迷宫中的宝物。

但是，开凿门是一件很费力费时的工作，ACM想开凿尽量少的门取出宝物，现在请你写一个程序来帮助它判断一下最少需要开几个门吧。

Input

第一行输入一个正数N(N<10)表示测试数据组数       每组测试数据的第一行是一个整数n(0<=n<=30),代表了墙的个数，随后的n行里每行有四个整数x1,x2,y1,y2，这四个数分别是代表一个墙的两个端点的坐标。外围的正方形四个顶点固定在(0,0)(0,100)(100,0)(100,100)这四堵个墙不在上面的n个数里。注意，不能在两个线的交点处开凿门。       数据保证任意两个中间墙的交点不在四周的墙上。       输完所有的墙后，输入两个数，x,y（可能不是整数），表示宝藏的坐标。 Output      输出最少需要开凿的门的个数。 Sample Input 1 7  20 0 37 100  40 0 76 100  85 0 0 75  100 90 0 90  0 71 100 61  0 14 100 38  100 47 47 100  54.5 55.4  Sample Output 2 Hint  线段相交、枚举 Source poj 1066

题解：

直接枚举所有墙的端点+宝物的位置作为一条线段， 求出与之相交的最少线段数。就是答案。

Poj的数据较强。

需要注意的点：

1.即使墙的数目为0，也需要知道宝物的位置。

2.Poj这道题是输入一组数据，但是好像是多线程。

3.判断相交直接叉积小于0就好。

#include #include #include #include using namespace std;const int N = 35;const int INF = 0xffffff;const double eps = 1e-8;struct POINT{ double x, y;};struct LINE{ POINT a, b;}l[N];int n;double cross(POINT o, POINT a, POINT b){ return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);}int Judge(POINT X, POINT Y){ int ans = 0; for(int i = 0; i < n; i ++){// printf("cross = %.2lf\n", cross(X, l[i].a, l[i].b) * cross(Y, l[i].a, l[i].b)); if(cross(X, l[i].a, l[i].b) * cross(Y, l[i].a, l[i].b) < -eps) ans ++; }// printf("ans = %d\n", ans); return ans;}int main(){ int T; scanf("%d", &T); while(T --){ scanf("%d", &n); if(n == 0){ puts("1"); continue; } for(int i = 0; i < n; i ++){ scanf("%lf %lf %lf %lf", &l[i].a.x, &l[i].a.y, &l[i].b.x, &l[i].b.y); } POINT d; scanf("%lf %lf", &d.x, &d.y); int ans = INF; for(int i = 0; i < n; i++){ ans = min(Judge(l[i].a, d), ans); ans = min(Judge(l[i].b, d), ans);// printf("ans = %d\n", ans); } printf("%d\n", ans + 1); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。