POJ1066 Treasure Hunt

题目大意：

　　一个正方形迷宫里的某一个点处藏有宝藏，但是这个迷宫除了边界四周有强外，内部还有一些交错的内墙，把迷宫分隔成小房间。如图所示。求问要从迷宫外通至宝藏处最少要穿过多少堵墙，而且穿墙的要求是：只能在房间边界的中点处砸开一扇门。

显然图示的例子需要穿过两堵墙。

输入：只含一个用例。第一行整数n(0<=n<=30)表示内墙数，接下来n行每行的4个整数为墙起点和终点的坐标: x1 y1 x2 y2. 迷宫四个顶点的坐标分布是(0, 0) (0, 100) (100, 0) (100, 100)。内墙的起点和终点均不在正方形的顶点上。内墙总是从正方形的四条边(外墙)中的一条出发到达另一条。不存在三条以上墙相交与一点的情况。墙不存在重合的情况。最后一行两个浮点数表示宝藏的坐标。宝藏不位于任何一堵墙上。

输出：Number of doors = k, 其中k为求得的最少墙数。

Sample Input

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

Number of doors = 2

　　本题比较直接的思路是以所有线段终点以及宝藏点为顶点，可达关系为边建立一个图，然后求宝藏点到各位于外墙上的点处的最短路径，然后选出最小的一个。不过这种方法比较耗时，实现起来也麻烦一些，有一种更简单的方法：

　　先还是要求出外墙上每一段墙的中点，然后通过把中点与宝藏点连起来，形成一条线段，求线段与内墙交点的最少数目，求得最小值后加1即可得所需答案。

在求外墙中点时可以先对所有内墙顶点包括四边形顶点按极角排序。极角的相关背景：可以参考这里。

然后依次求各中点与所有内墙的相交点个数，选最小值。所以问题最终化为“判断两条线段是否相交”。我的做法是利用中学数学里的线段参数方程。

线段pq上的点满足参数方程：x = xp + t*(xq - xp); y = yp + t*(yq - yp). 其中 t 在[0,1]内。

若线段 p1q1 与线段 p2q2 相交，则方程组：

xp1 + t * (xq1 - xp1) = xp2 + r * (xq2 - xp2);

yp1 + t * (yq1 - yp1) = yp2 + r * (yq2 - yp2);

求出其中的 t 如果满足 t >= 0 && t <= 1，则说明线段相交。最傻的办法了吧，不知道还有其它简单的方法吗？

 1 //////////////////////////////////////////////////////////////
 2 //        POJ1066 Treasure Hunt
 3 //        Memory: 744K        Time: 110MS
 4 //        Language: G++        Result : Accepted
 5 //////////////////////////////////////////////////////////////
 6 
 7 #include <iostream>
 8 #include <algorithm>
 9 
10 using namespace std;
11 
12 struct  Point {
13     double x, y;
14 } points[65];
15 
16 struct Line {
17     Point p, q;
18 } lines[30];
19 
20 int p_cnt, l_cnt, min_p;
21 double eps = 1e-8, t_x, t_y;
22 
23 bool cmp(const Point &a, const Point &b) {
24     //极角比较, 极角相等时，按距离排
25     long long xmult = a.x * b.y - b.x * a.y;
26     if (xmult == 0) {
27         if (a.y == 0 && b.y == 0) {
28             return a.x < b.x;
29         } else if (a.x == 100 && b.x == 100) {
30             return a.y < b.y;
31         } else if (a.y == 100 && b.y == 100) {
32             return a.x > b.x;
33         } else {
34             return a.y > b.y;
35         }
36     } else {
37         return xmult > 0;
38     }
39 }
40 
41 bool intersect(Line &l1, Line &l2) {
42     //利用线段的参数方程求解
43     double xp1 = l1.p.x, xp2 = l2.p.x, xq1 = l1.q.x, xq2 = l2.q.x;
44     double yp1 = l1.p.y, yp2 = l2.p.y, yq1 = l1.q.y, yq2 = l2.q.y;
45     double denominator = (yq2 - yp2) * (xq1 - xp1) - (yq1 - yp1) * (xq2 - xp2);
46     if (denominator < eps && denominator > -1 * eps) {
47         return false;    //分母为0，平行
48     }
49     double t = ((yp1 - yp2) * (xq2 - xp2) + (yp2 - yq2) * (xp1 - xp2)) / denominator;
50     if (t >= eps && t <= 1) { //参数t在0到1之间，说明线段相交
51         return true;
52     }
53     return false;
54 }
55 
56 int main(void) {
57     cin >> l_cnt;
58     p_cnt = 2 * l_cnt;
59     min_p = l_cnt;
60     for (int i = 0; i < l_cnt; ++i) {
61         cin >> points[2 * i].x >> points[2 * i].y;
62         lines[i].p = points[2 * i];
63         cin >> points[2 * i + 1].x >> points[2 * i + 1].y;
64         lines[i].q = points[2 * i + 1];
65     }
66     p_cnt += 4;
67     //将顶点坐标加入
68     points[p_cnt - 1] = { 0, 0 };
69     points[p_cnt - 2] = { 0, 100 };
70     points[p_cnt - 3] = { 100, 0 };
71     points[p_cnt - 4] = { 100, 100 };
72 
73     cin >> t_x >> t_y;
74     sort(points, points + p_cnt, cmp);
75     points[p_cnt] = { 0, 0 };
76     for (int i = 0; i < p_cnt; ++i) {
77         //中点
78         points[i].x = (points[i].x + points[i + 1].x) / 2;
79         points[i].y = (points[i].y + points[i + 1].y) / 2;
80         Line l = { points[i], { t_x, t_y } };
81         int i_cnt = 0;
82         for (int j = 0; j < l_cnt; ++j) {
83             if (intersect(l, lines[j])) {
84                 ++i_cnt;
85             }
86         }
87         min_p = min_p > i_cnt ? i_cnt : min_p;
88     }
89     cout << "Number of doors = " << min_p + 1 << endl;
90     return 0;
91 }

View Code

此外用C++提交一直Compile Error，G++ AC，还没想明白哪里的问题. =。=...