POJ 3347 Kadj Squares
判断线段与线段相交、射线与线段相交。我在做题的过程中用了二分猜答案再验证的方法。
原题地址：http://poj.org/problem?id=3347
POJ 3347 Kadj 正方形
题目描述
第一象限中有若干个正方形，这些正方形都是斜着摆放的（如图）。正方形下方与 x 轴刚好相交，其横坐标为 b1, b2, …, bi. 其中 b1 的值是这样取的：当第 1 个正方形的左边端点刚好在 y 轴上时，此时该正方形下面的端点与 x 轴相交，横坐标即为 b1. 接下来的 bi 的值应该取得尽量小，并且让该正方形与之前的任何正方形没有相交，并且 bi > bi-1.
题目的要求是找出那些能够从上方竖直往下看，能够被看到的正方形，不管是能完全被看到还是部分被看到。当然这个“看”指的不是透视图的看，而是一个“直线摄像机”的那种感觉……或者可以这样想，在相当高的一个地方，一个点竖直落下之后能够砸到某个正方形（砸到一个正方形之后这个点不会弹开，而是消失掉，以免砸到其它正方形），那么这个正方形就是可以被看到的。
图中 S1, S2, S4 就是能被看到的。
解题思路
首先需要知道数列 b1, b2, …, bi 的值，这个好取，直接按照定义按部就班地来。然后在所有正方形排列好之后，判断每个正方形是否会被看到。
下面谈谈具体的操作。由于给的是正方形的边长，而且还是整数，而且正方形都是 45° 旋转之后摆放的，为了方便，我们可以将边长乘以根号二，这样每个端点的坐标就都是整数了。事实上，为了方便讨论，我们还要再把边长乘以二，这样能方便我们判断正方形是否能被看到。
也就是说，输入的正方形边长被我们乘以了 [latex]2 \sqrt{2}[/latex] . 这个根号二好理解，而为什么是两倍的根号二呢……
因为我判断一个正方形是否能被看到的时候，先一一枚举 x 值，再枚举一个横坐标为当前 x 的一个相当高的点 P, 然后枚举一个在 P 点竖直下方的点 Q, 且 Q 高于 x 轴，作线段 PQ, 如果线段 PQ 只与一个正方形相交（无论是规范还是非规范相交），那么可以判断这个正方形是能被看到的；如果不与任何正方形相交或者与多个正方形相交的话，就二分枚举 Q 点再判断相交。
以这种方式判断相交，如果正方形边长不乘以二，并且遇到如图情况，就会判断出错；而如果乘以二，这些情况都能解决。（并不一定只有这两种特殊情况。）
POJ 3347 某种特殊情况①
POJ 3347 某种特殊情况②
源代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 | #include <algorithm> #include <cstdlib> #include <cstring> #include <cstdio> #include <vector> #include <cmath> using namespace std; #define inf 10000 struct point { int x, y; point() { } point(int a, int b) : x(a), y(b) { } point operator-(const point &p) const { return point(x - p.x, y - p.y); } }; struct line { point a, b; line() { } line(const point &x, const point &y) : a(x), b(y) { } point vec() const { return b - a; } }; struct square { int b; // Bottom coordinate. int s; // Side length / sqrt(2) * 2. point pnt(size_t i) const { switch (i % 4) { case 0: return point(b, 0); case 1: return point(b + s, s); case 2: return point(b, s * 2); } // case 3: return point(b - s, s); } line lne(size_t i) const { return line(pnt(i), pnt(i + 1)); } }; inline int sgn(int a) { return a > 0 ? 1 : a < 0 ? -1 : 0; } inline int cross(const point &a, const point &b) { return a.x * b.y - b.x * a.y; } inline int dot(const point &a, const point &b) { return a.x * b.x + a.y * b.y; } inline int abs(int a) { return a < 0 ? -a : a; } inline int relps(const point &p, const line &s) { int rp = sgn(cross(p - s.a, s.vec())); // -1 left, 1 right. if (rp) return 3 * rp; point psa(s.a - p), psb(s.b - p); int r = sgn(dot(psa, psb)); if (r < 0) return 0; // Std intersect. if (r == 0) return 1; // At end-points. return 2; // On line but not segment. } inline int relss(const line &sa, const line &sb) { int saa = relps(sa.a, sb); int sab = relps(sa.b, sb); int sba = relps(sb.a, sa); int sbb = relps(sb.b, sa); if (saa * sab == -9 && sba * sbb == -9) return 0; // Intersects (standard). char state[4] = {0}; ++state[abs(saa)]; ++state[abs(sab)]; ++state[abs(sba)]; ++state[abs(sbb)]; if (state[0] == 0 && state[1] == 0) return 2; // No intersection. return 1; // N-Std intersects. } inline int relsqr(const square &sa, const square &sb) { for (size_t i = 0; i < 4; ++i) { for (size_t j = 0; j < 4; ++j) { if (!relss(sa.lne(i), sb.lne(j))) return 0; // Intersects. } } return 1; // Others. } inline int relsegsqr(const line &seg, const square &sqr) { for (size_t i = 0; i < 4; ++i) { if (relss(seg, sqr.lne(i)) < 2) return 0; // Intersects. } return 1; // Others. } #define N 50 square sq[N+1]; size_t n; inline size_t seewhat(int x, int y = inf) { int a = y - 1, b = 0, m = a / 2; size_t seethis, howmany = 0; while (a >= b) { line seg(point(x, y), point(x, m)); howmany = 0; for (size_t i = 1; i <= n; ++i) { if (!relsegsqr(seg, sq[i])) { ++howmany; seethis = i; } } if (howmany == 1) return seethis; if (howmany > 1) b = m + 1; else a = m - 1; m = (a + b) / 2; } return 0; } inline bool anyintersection(size_t m, int b) { sq[m].b = b; for (size_t i = 1; i < m; ++i) if (!relsqr(sq[m], sq[i])) return true; return false; } int main(int argc, char *argv[]) { while (scanf("%lu", &n)) { if (n == 0) break; for (size_t i = 1; i <= n; ++i) { scanf("%d", &sq[i].s); sq[i].s *= 2; } int b = sq[1].s; for (size_t i = 1; i <= n; ++i) { while (anyintersection(i, b)) ++b; sq[i].b = b++; } int e = sq[n].b + sq[n].s; vector<size_t> result; for (int i = 0; i <= e; ++i) { size_t w = seewhat(i); if (w) result.push_back(w); } sort(result.begin(), result.end()); vector<size_t>::iterator it = unique(result.begin(), result.end()); result.resize(it - result.begin()); printf("%lu", result[0]); for (size_t k = 1; k < result.size(); ++k) printf(" %lu", result[k]); printf("\n"); } return EXIT_SUCCESS; } |
原创文章，转载请注明来源：http://euyuil.com/2441/poj-3347-kadj-squares/
看到你的程序就觉得这不是一个水题了…
确实不算水。
自己写的题解？那个配图好专业啊！