计算几何题目，特别要注意障碍物位于House Line上方或者Property Line下方时要首先排除。
http://poj.org/problem?id=2074
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <queue> 5 6 using namespace std; 7 const int maxn = 1e6; 8 9 double Hx1, Hx2, Hy, Px1, Px2, Py; 10 struct Point{ 11 double x1, x2; 12 Point(double x1 = 0, double x2 = 0) : x1(x1), x2(x2) {} 13 bool operator < (const Point& rhs) const{ 14 return x1 < rhs.x1 || (x1 == rhs.x1 && x2 < rhs.x2); 15 } 16 Point operator - (const Point& rhs) const{ 17 return Point(x1 - rhs.x1, x2 - rhs.x2); 18 } 19 }; 20 Point s[maxn]; 21 int n, k; 22 double x1, x2, y; 23 24 double Cross(Point a, Point b) { return a.x1 * b.x2 - b.x1 * a.x2; } 25 26 double getPosR(double x, double y){ 27 Point vect1 = Point(Hx1, Hy) - Point(x, y); 28 Point vect2 = Point(Px2, Py) - Point(Hx1, Hy); 29 if(Cross(vect1, vect2) >= 0) return Px2; 30 Point vect3 = Point(Px1, Py) - Point(Hx1, Hy); 31 if(Cross(vect1, vect3) <= 0) return Px1; 32 return (x - Hx1) * (Py - Hy) / (y - Hy) + Hx1; 33 } 34 35 double getPosL(double x, double y){ 36 Point vect1 = Point(Hx2, Hy) - Point(x, y); 37 Point vect2 = Point(Px2, Py) - Point(Hx2, Hy); 38 if(Cross(vect1, vect2) >= 0) return Px2; 39 Point vect3 = Point(Px1, Py) - Point(Hx2, Hy); 40 if(Cross(vect1, vect3) <= 0) return Px1; 41 return (x - Hx2) * (Py - Hy) / (y - Hy) + Hx2; 42 } 43 44 int main(){ 45 freopen("in.txt", "r", stdin); 46 while(~scanf("%lf%lf%lf", &Hx1, &Hx2, &Hy) && (Hx1 + Hx2 + Hy)){ 47 scanf("%lf%lf%lf", &Px1, &Px2, &Py); 48 scanf("%d", &n); 49 k = 0; 50 for(int i = 0; i < n; i++){ 51 scanf("%lf%lf%lf", &x1, &x2, &y); 52 if(y >= Hy || y <= Py) continue; 53 double tx1 = getPosL(x1, y); 54 double tx2 = getPosR(x2, y); 55 if(tx1 != tx2) s[k++] = Point(tx1, tx2); 56 } 57 if(!k){ 58 printf("%.2f ", Px2 - Px1); 59 continue; 60 } 61 sort(s, s + k); 62 double ans = s[0].x1 - Px1; 63 for(int i = 0; i < k; i++){ 64 double rear = s[i].x2; 65 int j = i; 66 while(i + 1 < k && s[i + 1].x2 <= rear) ++i; 67 if(i == k - 1){ 68 ans = max(ans, Px2 - rear); 69 break; 70 } 71 double front = s[i + 1].x1; 72 if(front > rear) ans = max(ans, front - rear); 73 } 74 if(!ans) puts("No View"); 75 else printf("%.2f ", ans); 76 } 77 return 0; 78 }