POJ 2074 Line of Sight
这道题目的大意是，一个人在路边建造了一栋房子，他希望他的房子被路过这条路的人看见。然而在房子和路之间的障碍会阻挡路人的视线。他想要你计算在这条路上，行人能够完整地看到他的房子的最长的一段连续的路段的长度。
路、障碍、房子都被表示成平行于 x 轴的线段，如图：
POJ 2074 示意图
原题地址：http://poj.org/problem?id=2074
解题思路
这个题目要注意的地方，就是这些障碍物可能会给在房子的上方、路的下方，并且有的障碍物可能永远挡不住房子，而有的障碍物可能会完全挡住房子。
我的思路是，先把房子和路的信息记下。然后，在读取每个障碍物信息的时候，计算这个障碍物能够挡住路的哪部分。看图：
POJ 2074 一般情况
当然上面那种是一般情况，就是说，那两条绿色的线的交点在路的线段上。如果有特殊情况，交点在路的延长线上，那么就要认为，被挡住的部分是在路的线段相应的端点上。
我写了一个 struct, 记下了每个这种看不见的路段的端点的坐标，并且还记录了一个额外的整数信息。如果这个端点是左端点，那么这个整数是 -1, 反之是 1. 也就是：
1 2 3 4 | struct pinfo { point p; // 端点坐标 int i; // 左端点则记 1, 右端点则记 -1 }; |
然后我弄了一个 vector
然后对这个 vector 排序，关键字是端点坐标的 x 值。最后把这个 vector 扫一遍，定义一个临时变量 int fl; 见到一个左端点就 ++fl, 见到一个右端点就 –fl. 如果 fl 是 0 的时候，说明这段路是能够完全看到房子的。
源代码
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 | #include <cstdlib> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> #include <cmath> using namespace std; struct point { double x, y; point(double a, double b) : x(a), y(b) { } point() { } double magsqr() const { return x * x + y * y; } double mag() const { return sqrt(magsqr()); } point operator-(const point &p) const { return point(x - p.x, y - p.y); } point operator*(double k) const { return point(x * k, y * k); } point operator/(double k) const { return point(x / k, y / k); } }; struct line { point a, b; line() { } line(const point &x, const point &y) : a(x), b(y) { } point vec() const { return b - a; } }; const double eps = 1e-8; inline int sgn(double a) { return a > eps ? 1 : a < -eps ? -1 : 0; } inline double cross(const point &a, const point &b) { return a.x * b.y - b.x * a.y; } inline point inpll(const line &a, const line &b) { double u = cross(a.vec(), point(b.b - a.b)); double v = cross(a.vec(), point(b.a - a.b)); return (b.b * v - b.a * u) / (v - u); } struct pinfo { point p; int i; }; line ho, pr, ob; size_t n; vector<pinfo> pfs; inline void fixpoint(point &p) { if (p.x > pr.b.x) p.x = pr.b.x; if (p.x < pr.a.x) p.x = pr.a.x; } bool lessthanpfs(const pinfo &a, const pinfo &b) { return a.p.x < b.p.x; } inline bool test() { cin >> ho.a.x >> ho.b.x >> ho.a.y; ho.b.y = ho.a.y; if (ho.a.x == 0.0 && ho.b.x == 0.0 && ho.a.y == 0.0) return false; cin >> pr.a.x >> pr.b.x >> pr.a.y; pr.b.y = pr.a.y; cin >> n; size_t i; pfs.clear(); pinfo pf; for (i = 0; i < n; ++i) { cin >> ob.a.x >> ob.b.x >> ob.a.y; ob.b.y = ob.a.y; if (sgn(ob.a.y - ho.a.y) >= 0) continue; if (sgn(ob.a.y - pr.a.y) <= 0) continue; point ptl = inpll(pr, line(ho.b, ob.a)); point ptr = inpll(pr, line(ho.a, ob.b)); fixpoint(ptl); fixpoint(ptr); pf.p = ptl; pf.i = 1; pfs.push_back(pf); pf.p = ptr; pf.i = -1; pfs.push_back(pf); } pf.p = pr.b; pf.i = 1; pfs.push_back(pf); sort(pfs.begin(), pfs.end(), lessthanpfs); int fl = 0; double mx = 0.0, cu = pr.a.x, t; for (size_t i = 0; i < pfs.size(); ++i) { if (fl > 0 && fl + pfs[i].i == 0) { cu = pfs[i].p.x; } else if (fl == 0) { t = pfs[i].p.x - cu; mx = max(mx, t); } fl += pfs[i].i; } if (!sgn(mx)) cout << "No View" << endl; else printf("%0.2f\n", mx); return true; } int main(int, char *[]) { freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); while (test()); return EXIT_SUCCESS; } |
原创文章，转载请注明来源：http://euyuil.com/2651/poj-2074-line-of-sight/
