首页 > 代码库 > 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 */
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。