poj2074

题目大意：从下面的一条直线看最上面的一条直线，中间有很多平行的障碍直线，问下面直线有多长是可以看到最上面的整条直线。。

思路：对于中间的每条直线求看不到的长度，最后求交集即可

code：

 1 /*
 2   State:Accepted
 3   Time:2013-03-30 00:51:14
 4 */
 5 #include <iostream>
 6 #include <fstream>
 7 #include <cstring>
 8 #include <cstdio>
 9 #include <cmath>
10 #include <algorithm>
11 #include <string>
12 #include <cstdlib>
13 #define eps 1e-8
14 using namespace std;
15 struct oo{double x1, x2, y;};
16 
17 double tx1 , ty ,tx2, dx1, dx2 ,dy;
18 oo a[1500], b[1500];
19 int n;
20 void init(){
21    scanf("%lf%lf%lf",&dx1, &dx2, &dy);
22    scanf("%d",&n);
23    for (int i = 1;  i <= n ; ++i)
24        scanf("%lf%lf%lf",&a[i].x1, &a[i].x2, &a[i].y);
25 }
26 
27 double work_x(double x1, double y1, double y2){
28       double x2 = (x1*y2/y1);
29       return x2;
30 }
31 
32 bool cmp(const oo a, const oo b){
33     if (a.x1 < b.x1) return true;
34     if (fabs(a.x1 - b.x1) < eps && a.x2 > b.x2) return true;
35     return false;
36  }
37 
38 void solve(){
39    memset(b, 0 ,sizeof(b));
40    for (int i = 1; i <= n ; ++i ){
41          if (a[i].y >= ty - eps || a[i].y <= dy - eps) continue;
42          if ((a[i].y - dy) < eps){
43               b[i].x1 = a[i].x1;
44               b[i].x2 = a[i].x2;
45          } else {
46                   b[i].x2 = a[i].x2 - work_x(tx1 - a[i].x2, ty - a[i].y , a[i].y - dy);
47                   b[i].x1 = a[i].x1 -  work_x(tx2 - a[i].x1, ty - a[i].y , a[i].y - dy);
48                 }
49          b[i].x2 = max(dx1,b[i].x2);
50          b[i].x2 = min(dx2,b[i].x2);
51          b[i].x1 = max(dx1,b[i].x1);
52          b[i].x1 = min(dx2, b[i].x1);
53    }
54    /*for (int  i = 1; i <=  n; ++i)
55       printf("%.2lf  %.2lf\n", b[i].x1 ,b[i].x2);*/
56    sort(b+1, b+n+1,  cmp);
57    double ans =0, LL= 0 , x = dx1;
58    for (int i = 1; i <= n; ++i){
59       if (b[i].x2 <= x) continue;
60       if (b[i].x1 > x){
61                   LL = b[i].x1 - x;
62                   ans = max(ans , LL);
63                   x = b[i].x1;
64                   }
65       x = b[i].x2; 
66    }
67    ans = max(ans , dx2 - x);
68    if (fabs(ans) < eps) printf("No View\n");
69    else printf("%.2f\n",ans);
70 }
71 
72 int main(){
73     freopen("poj2074.in","r",stdin);
74     freopen("poj2074.out","w",stdout);
75     while (~scanf("%lf%lf%lf",&tx1, &tx2, &ty )){
76         if (fabs(tx1)<eps && fabs(tx2)<eps && fabs(ty)<eps) break;
77         init();
78         solve();
79     }
80     fclose(stdin); fclose(stdout);
81 }