龙泉驿网站seo,海口seo网站推广,建设银行银监会官方网站,阿里云虚拟主机如何安装wordpress给定两个点: typedef struct { double x, y; } Point; Point A1,A2,B1,B2; 首先引入两个实验#xff1a; a.快速排斥实验 设以线段A1A2和线段B1B2为对角线的矩形为M,N; 若M,N 不相交#xff0c;则两个线段显然不相交#xff1b; 所以#xff1a;满足第一个条件时#xf…给定两个点: typedef struct { double x, y; } Point; Point A1,A2,B1,B2; 首先引入两个实验 a.快速排斥实验 设以线段A1A2和线段B1B2为对角线的矩形为M,N; 若M,N 不相交则两个线段显然不相交 所以满足第一个条件时两个线段可能相交。 b.跨立实验 如果两线段相交则两线段必然相互跨立对方.若A1A2跨立B1B2则矢量( A1 - B1 ) 和(A2-B1)位于矢量(B2-B1)的两侧 即(A1-B1) × (B2-B1) * (A2-B1) × (B2-B1)0。 上式可改写成(A1-B1) × (B2-B1) * (B2-B1) × (A2-A1)0。 应该判断两次即两条线段都要为直线判断另一直线的两端点是否在它两边若是则两线段相交。 若积极满跨立实验是不行的如下面的情况 即两条线段在同一条直线上。所以我们要同时满足两次跨立和快速排斥实验。 总体分析 当(A1-B1) × (B2-B1)0时说明(A1-B1)和(B2-B1)共线但是因为已经通过快速排斥试验所以 A1一定在线段 B1B2上同理(B2-B1)×(A2-B1)0 说明A2一定在线段B1B2上。所以判断A1A2跨立B1B2的依据是(A1-B1) × (B2-B1) * (B2-B1) × (A2-B1) 0。 同理判断B1B2跨立A1A2的依据是(B1-A1) × (A2-A1) * (A2-A1) × (B2-A1) 0。 如图 应用 1. 判断两个线段相交 2. 判断线段与直线相交 3. 判断点在矩形内 模板题 1 #includebits/stdc.h2 using namespace std;3 typedef long long ll;4 struct line{5 double x1,y1,x2,y2;6 }p,q;7 double cross1(line a,line b){8 return (a.x1-b.x1)*(b.y2-b.y1)-(a.y1-b.y1)*(b.x2-b.x1);9 }
10 double cross2(line a,line b){
11 return (a.x2-b.x1)*(b.y2-b.y1)-(a.y2-b.y1)*(b.x2-b.x1);
12 }
13 bool judge(line a,line b){
14 if(max(a.x1,a.x2)min(b.x1,b.x2)
15 max(a.y1,a.y2)min(a.y1,a.y2)
16 max(b.x1,b.x2)min(a.x1,a.x2)
17 max(b.y1,b.y2)min(a.y1,a.y2)
18 cross1(a,b)*cross2(a,b)0
19 cross1(b,a)*cross2(b,a)0)
20 return true;
21 return false;
22 }
23 int main(){
24 int t;
25 cint;
26 while(t--){
27 cinp.x1p.y1p.x2p.y2q.x1q.y1q.x2q.y2;
28 if(judge(p,q)) coutYes\n;
29 else coutNo\n;
30 }
31 } 转载于:https://www.cnblogs.com/elpsycongroo/p/6914812.html
