提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  大数据

当前栏目

nyoj 83-迷宫寻宝（二） （计算几何， 叉积）

计算 几何 nyoj 迷宫 83
2023-09-11 14:21:11 时间

83-迷宫寻宝（二）


内存限制:10MB 时间限制:1000ms 特判: No
通过数:2 提交数:6 难度:5

题目描述:

一个叫ACM的寻宝者找到了一个藏宝图，它根据藏宝图找到了一个迷宫，这是一个很特别的迷宫，迷宫是一100*100的个正方形区域，里面有很多墙，这些墙都是由一些直线构成的，如下图。
 

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

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

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

输入描述:

第一行输入一个正数N(N<10)表示测试数据组数
每组测试数据的第一行是一个整数n(0<=n<=30),代表了墙的个数，随后的n行里每行有四个整数x1,x2,y1,y2，这四个数分别是代表一个墙的两个端点的坐标。外围的正方形四个顶点固定在(0,0)(0,100)(100,0)(100,100)这四堵个墙不在上面的n个数里。注意，不能在两个线的交点处开凿门。
数据保证任意两个中间墙的交点不在四周的墙上。
输完所有的墙后，输入两个数，x,y（可能不是整数），表示宝藏的坐标。

输出描述:

输出最少需要开凿的门的个数

样例输入:

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

样例输出:

2

分析：
　　1、我们可以通过叉积来判断线段是否相交
　　PS：
　　　　
 1 node A, B;
 2 struct line
 3 {
 4     node a, b;
 5 }L[100];
 6 int cross_product(node A, node B, node C)
 7 {
 8     return ((A.x - B.x) * (A.y - C.y) - (A.y - B.y) * (A.x - B.x));
 9 }
10 if (cross_product(A, L[i].a, L[i].b) * cross_product(B, L[i].a, L[i].b) < -EPS) // 判断是否相交
11 {
12     ++ cnt;
13 }

　　2、遍历所有的点，即就可以得到最短的组合


C/C++代码实现（AC）：
 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstring>
 4 #include <cstdio>
 5 #include <cmath>
 6 #include <stack>
 7 #include <map>
 8 #include <queue>
 9 #include <set>
10 #include <climits>
11 
12 using namespace std;
13 const int MAXN = 35;
14 const int MY_MAX = INT_MAX;
15 const int EPS = 1e-8;
16 int N, n;
17 
18 struct node
19 {
20     double x, y;
21 };
22 
23 struct line
24 {
25     node a, b;
26 }l[MAXN];
27 
28 int cross_product(node A, node B, node C)
29 {
30     return ((B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x));
31 }
32 
33 int solve(node K, node A)
34 {
35     int cnt = 1;
36     for(int i = 0; i < n; ++ i)
37     {
38         if (cross_product(A, l[i].a, l[i].b) * cross_product(K, l[i].a, l[i].b) < -EPS)
39             ++ cnt;
40     }
41     return cnt;
42 }
43 
44 int main()
45 {
46     scanf("%d", &N);
47     while(N --)
48     {
49         int cnt = MY_MAX;
50         scanf("%d", &n);
51         for(int i = 0; i < n; ++ i)
52             scanf("%lf%lf%lf%lf", &l[i].a.x, &l[i].a.y, &l[i].b.x, &l[i].b.y);
53         node k;
54         scanf("%lf%lf", &k.x, &k.y);
55         if (n == 0)
56             printf("1\n");
57         else
58         {
59             for(int i = 0; i < n; ++ i)
60             {
61                 cnt = min(cnt, solve(k, l[i].a));
62                 cnt = min(cnt, solve(k, l[i].b));
63             }
64             printf("%d\n", cnt);
65         }
66     }
67     return 0;
68 }

 

相关文章