题意是，在一个金字塔中有一个宝藏，金字塔里面有很多的墙，要穿过墙壁才能进入到宝藏所在的地方。可是因为某些原因，只能在两个墙壁的交点连线的中点穿过墙壁。问最少要穿过多少墙壁才能得到宝藏。
比较容易想到的一个办法就是直接用中点构图，然后判断点与点之间是否能够直接相连，最后bfs得到最小距离。
我的代码也是这样做，结果相当险的900+ms通过。
代码如下：
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 #include <cmath> 6 7 using namespace std; 8 9 const double EPS = 1e-8; 10 const int N = 55; 11 inline int sgn(double x) { return (x > EPS) - (x < -EPS);} 12 13 struct Point { 14 double x, y; 15 Point() {} 16 Point(double x, double y) : x(x), y(y) {} 17 bool operator < (Point a) const { return sgn(x - a.x) < 0 || sgn(x - a.x) == 0 && y < a.y;} 18 bool operator == (Point a) const { return sgn(x - a.x) == 0 && sgn(y - a.y) == 0;} 19 Point operator + (Point a) { return Point(x + a.x, y + a.y);} 20 Point operator - (Point a) { return Point(x - a.x, y - a.y);} 21 Point operator * (double p) { return Point(x * p, y * p);} 22 Point operator / (double p) { return Point(x / p, y / p);} 23 } ; 24 inline double cross(Point a, Point b) { return a.x * b.y - a.y * b.x;} 25 inline double dot(Point a, Point b) { return a.x * b.x + a.y * b.y;} 26 inline double veclen(Point a) { return sqrt(dot(a, a));} 27 inline Point vecunit(Point x) { return x / veclen(x);} 28 inline Point normal(Point x) { return Point(-x.y, x.x) / veclen(x);} 29 inline bool onseg(Point x, Point a, Point b) { return sgn(cross(a - x, b - x)) == 0 && sgn(dot(a - x, b - x)) <= 0;} 30 31 struct Line { 32 Point s, t; 33 Line() {} 34 Line(Point s, Point t) : s(s), t(t) {} 35 Point vec() { return t - s;} 36 Point point(double p) { return s + vec() * p;} 37 } ; 38 inline bool onseg(Point x, Line l) { return onseg(x, l.s, l.t);} 39 inline Point llint(Line a, Line b) { return a.point(cross(b.vec(), a.s - b.s) / cross(a.vec(), b.vec()));} 40 41 Point ips[N][N], trs, vex[N * N]; 42 bool out[N * N]; 43 int ipcnt[N], vexcnt; 44 Line ls[N]; 45 46 void input(int &n) { 47 Point tmp[2]; 48 for (int i = 0; i < n; i++) { 49 for (int j = 0; j < 2; j++) cin >> tmp[j].x >> tmp[j].y; 50 ls[i] = Line(tmp[0], tmp[1]); 51 } 52 ls[n++] = Line(Point(0.0, 0.0), Point(100.0, 0.0)); 53 ls[n++] = Line(Point(100.0, 0.0), Point(100.0, 100.0)); 54 ls[n++] = Line(Point(100.0, 100.0), Point(0.0, 100.0)); 55 ls[n++] = Line(Point(0.0, 100.0), Point(0.0, 0.0)); 56 cin >> trs.x >> trs.y; 57 } 58 59 inline Point mid(Point a, Point b) { return (a + b) / 2.0;} 60 61 int makevex(int n) { 62 Point tmp; 63 memset(ipcnt, 0, sizeof(ipcnt)); 64 for (int i = 0; i < n; i++) { 65 for (int j = 0; j < i; j++) { 66 if (sgn(cross(ls[i].vec(), ls[j].vec()))) { 67 tmp = llint(ls[i], ls[j]); 68 if (onseg(tmp, ls[i])) ips[i][ipcnt[i]++] = tmp; 69 if (onseg(tmp, ls[j])) ips[j][ipcnt[j]++] = tmp; 70 } 71 } 72 } 73 vexcnt = 0; 74 vex[vexcnt++] = trs; 75 memset(out, 0, sizeof(out)); 76 for (int i = 0; i < n; i++) { 77 ips[i][ipcnt[i]++] = ls[i].s; 78 ips[i][ipcnt[i]++] = ls[i].t; 79 sort(ips[i], ips[i] + ipcnt[i]); 80 for (int j = 1; j < ipcnt[i]; j++) { 81 if (ips[i][j - 1] == ips[i][j]) continue; 82 vex[vexcnt++] = mid(ips[i][j - 1], ips[i][j]); 83 } 84 } 85 // cout << vexcnt << endl; 86 for (int i = 0; i < vexcnt; i++) { 87 for (int j = n - 4; j < n; j++) { 88 if (onseg(vex[i], ls[j])) { 89 out[i] = true; 90 break; 91 } 92 } 93 } 94 // for (int i = 0; i < vexcnt; i++) cout << out[i]; cout << endl; 95 return vexcnt; 96 } 97 98 inline bool ssint(Line a, Line b) { return sgn(cross(a.s - b.s, a.t - b.s)) * sgn(cross(a.s - b.t, a.t - b.t)) < 0 99 && sgn(cross(b.s - a.s, b.t - a.s)) * sgn(cross(b.s - a.t, b.t - a.t)) < 0;} 100 101 bool mat[N * N][N * N]; 102 103 bool test(int i, int j, int n) { 104 Line tmp = Line(vex[i], vex[j]); 105 for (int a = 0; a < n; a++) 106 if (onseg(vex[i], ls[a]) && onseg(vex[j], ls[a])) return false; 107 for (int a = 0; a < n; a++) 108 if (ssint(tmp, ls[a])) return false; 109 return true; 110 } 111 112 void makemat(int n, int m) { 113 memset(mat, 0, sizeof(mat)); 114 for (int i = 0; i < n; i++) { 115 for (int j = 0; j < i; j++) { 116 if (test(i, j, m)) mat[i][j] = mat[j][i] = true; 117 } 118 } 119 // for (int i = 0; i < n; i++) { 120 // for (int j = 0; j < n; j++) cout << mat[i][j]; cout << endl; 121 // } 122 } 123 124 int q[N * N * N]; 125 bool vis[N * N]; 126 127 int bfs(int n) { 128 int qh, qt; 129 memset(vis, 0, sizeof(vis)); 130 qh = qt = 0; 131 q[qt++] = 0; 132 vis[0] = true; 133 int cnt = 0; 134 while (qh < qt) { 135 int sz = qt - qh; 136 cnt++; 137 for (int i = 0; i < sz; i++) { 138 int cur = q[qh++]; 139 // cout << cur << endl; 140 // cout << vex[cur].x << ' ' << vex[cur].y << endl; 141 for (int j = 0; j < n; j++) { 142 if (vis[j] || !mat[cur][j]) continue; 143 q[qt++] = j; 144 vis[j] = true; 145 if (out[j]) return cnt; 146 } 147 } 148 } 149 return -1; 150 } 151 152 int main() { 153 // freopen("in", "r", stdin); 154 int n; 155 while (cin >> n) { 156 input(n); 157 int m; 158 makemat(m = makevex(n), n); 159 cout << "Number of doors = " << bfs(m) << endl; 160 } 161 return 0; 162 }
——written by Lyon