首页 > 代码库 > poj2074Line of Sight(直线相交)

poj2074Line of Sight(直线相交)

链接

几何细节题。

对于每一个障碍物可以求出它在地产线上的覆盖区间,如下图。

紫色部分即为每个障碍物所覆盖掉的区间,求出所有的,扫描一遍即可。

几个需要注意的地方:直线可能与地产线没有交点,可视区间可能包含地产线的端点,扫描的时候保留当前扫到的最大值。

代码中的数据很经典,供参考。

  1 #include <iostream>  2 #include<cstdio>  3 #include<cstring>  4 #include<algorithm>  5 #include<stdlib.h>  6 #include<vector>  7 #include<cmath>  8 #include<queue>  9 #include<set> 10 using namespace std; 11 #define N 10100 12 #define LL long long 13 #define INF 0xfffffff 14 #define zero(x) (((x)>0?(x):-(x))<eps) 15 const double eps = 1e-8; 16 const double pi = acos(-1.0); 17 const double inf = ~0u>>2; 18 struct point 19 { 20     double x,y; 21     point(double x=0,double y=0):x(x),y(y) {} 22 } p[N]; 23 struct line 24 { 25     point u,v; 26 } li[N]; 27 typedef point pointt; 28 pointt operator -(point a,point b) 29 { 30     return point(a.x-b.x,a.y-b.y); 31 } 32 int dcmp(double x) 33 { 34     if(fabs(x)<eps) return 0; 35     return x<0?-1:1; 36 } 37 bool cmp(point a,point b) 38 { 39     if(dcmp(a.x-b.x)==0) 40         return a.y<b.y; 41     return a.x<b.x; 42 } 43  44 bool intersection1(point p1, point p2, point p3, point p4, point& p)      // 直线相交 45 { 46     double a1, b1, c1, a2, b2, c2, d; 47     a1 = p1.y - p2.y; 48     b1 = p2.x - p1.x; 49     c1 = p1.x*p2.y - p2.x*p1.y; 50     a2 = p3.y - p4.y; 51     b2 = p4.x - p3.x; 52     c2 = p3.x*p4.y - p4.x*p3.y; 53     d = a1*b2 - a2*b1; 54     if (!dcmp(d))    return false; 55     p.x = (-c1*b2 + c2*b1) / d; 56     p.y = (-a1*c2 + a2*c1) / d; 57     return true; 58 } 59 int main() 60 { 61     int i,n; 62     int x1,x2,y; 63     while(scanf("%d%d%d",&x1,&x2,&y)&&x1&&x2&&y) 64     { 65         li[1].u = point(x1,y); 66         li[1].v = point(x2,y); 67         li[1].v.y = li[1].u.y; 68         scanf("%lf%lf%lf",&li[2].u.x,&li[2].v.x,&li[2].u.y); 69         li[2].v.y = li[2].u.y; 70         scanf("%d",&n); 71         for(i = 3; i <= n+2; i++) 72         { 73             scanf("%lf%lf%lf",&li[i].u.x,&li[i].v.x,&li[i].u.y); 74             li[i].v.y = li[i].u.y; 75         } 76         n+=2; 77         int g = 0; 78         for(i = 3 ; i <= n; i++) 79         { 80             if(dcmp(li[i].u.y-li[1].u.y)>=0||dcmp(li[i].u.y-li[2].u.y)<=0) continue; 81             point pp; 82             intersection1(li[1].u,li[i].v,li[2].u,li[2].v,pp); 83             p[++g].y = min(li[2].v.x,max(pp.x,li[2].u.x)); 84             intersection1(li[1].v,li[i].u,li[2].u,li[2].v,pp); 85             p[g].x = max(li[2].u.x,min(li[2].v.x,pp.x)); 86         } 87         sort(p+1,p+g+1,cmp); 88         double maxz,ty ; 89        // cout<<p[1].x<<" "<<p[1].y<<endl; 90         if(g==0) 91         maxz = li[2].v.x-li[2].u.x; 92         else 93         { 94             maxz = max(p[1].x-li[2].u.x,li[2].v.x-p[g].y); 95             ty = p[1].y; 96         } 97  98         for(i = 1; i < g; i++) 99         {100            // printf("%.3f %.3f\n",p[i].x,p[i].y);101             ty = max(ty,p[i].y);102             if(p[i+1].x>ty)103             {104                 maxz = max(p[i+1].x-ty,maxz);//printf("%.3f %.3f\n",ty,maxz);105                 ty = p[i+1].y;106             }107 108         }109         if(dcmp(maxz)<=0)110             puts("No View");111         else112             printf("%.2f\n",maxz);113     }114     return 0;115 }116 /*117 2 6 6118 0 15 0119 3120 1 2 1121 3 4 1122 12 13 1123 1 5 5124 0 10 0125 1126 0 15 1127 2 6 6128 0 15 0129 3130 1 2 1131 3 4 1132 12 13 1133 2 6 6134 0 15 0135 4136 1 2 1137 3 4 1138 12 13 1139 1 5 2140 2 6 6141 0 15 0142 2143 0 5 3144 6 15 3145 2 6 6146 0 15 0147 2148 6 10 1149 0 2 1150 2 6 6151 0 15 0152 1153 2 6 7154 2 6 6155 0 15 0156 1157 2 6 7158 2 6 6159 0 15 0160 1161 4 4.5 5.5162 2 6 6163 0 15 0164 16165 0 1 3166 1.5 2 3167 2.5 3 3168 3.5 4 3169 4.5 5 3170 5.5 6 3171 6.5 7 3172 7.5 8 3173 8.5 9 3174 9.5 10 3175 10.5 11 3176 11.5 12 3177 12.5 13 3178 13.5 14 3179 14.5 15 3180 15.5 16 3181 2 6 6182 0 15 0183 16184 0 1 .1185 1.5 2 .1186 2.5 3 .1187 3.5 4 .1188 4.5 5 .1189 5.5 6 .1190 6.5 7 .1191 7.5 8 .1192 8.5 9 .1193 9.5 10 .1194 10.5 11 .1195 11.5 12 .1196 12.5 13 .1197 13.5 14 .1198 14.5 15 .1199 15.5 16 .1200 2 6 6201 0 15 0202 14203 0 1 3204 1.5 2 3205 2.5 3 3206 3.5 4 3207 4.5 5 3208 5.5 6 3209 8.5 9 3210 9.5 10 3211 10.5 11 3212 11.5 12 3213 12.5 13 3214 13.5 14 3215 14.5 15 3216 15.5 16 3217 2 6 6218 0 4000000000 0219 2220 1 2 1 221 15 16 3222 2 6 6223 0 15 1224 5225 1 1.5 6226 17 18 1 227 3 5 3228 0 20 10229 0 20 0.5230 231 答案:232 8.80233 No View234 8.80235 6.70236 No View237 4.00238 15.00239 15.00240 No View241 No View242 0.44243 1.00244 3999999970.00245 8.00246 */
View Code