判断两个线段是否是有交点 upc 2019年第二阶段我要变强个人训练赛第三场c题

题目描述 给定N个线段。求有交点的线段对数。 保证没有两条线段共线

输入 一行一个整数N，表示线段的个数 第2~N+1行，每行四个实数，x1,y1,x2,y2，表示线段的两个端点(x1,y1)和(x2,y2)

输出 一行一个整数，表示有交点的线段对数。

分析：https://www.cnblogs.com/wuwangchuxin0924/p/6218494.html 参考了上面的那一片文章，我在这里就简单的解释一下： 我们首先要知道向量的叉乘的意义 假设$a$$b$<0，说明$a$需要顺时针旋转才能到到$b$（角度是大于0小于180度的），那么$a$$a$>0,说明$a$需要逆时针旋转到达$b$

假设两个线段是ab和cd，那么$cb$、$ca$和$cd$都可以求出，那么我们只需要判断$cb$叉乘$cb$与$cb$叉乘$ca$的积是不是小于0的，那么这样就能保证ca与cb是在cb两边的； 同理还需要再去判断ac与ad是不是在ab的两端，只要是两个判断都符合，那么就能保证有交点了（当然对于这题来说够了，不需要去排斥）

还可以得到一个结论就是几何问题不要用除法，会卡精度的QAQ

#include <iostream> #include <algorithm> #include <string> #include <map> #include <cstring> #include <cmath> #include <queue> #include <cstdio> #include <vector> #include <set> #include <stack> using namespace std; typedef long long ll; const int INF=0x3f3f3f3f; const double esp=1e-8; struct node{ double x1,x2,y1,y2; }num[200]; struct node1{ double x,y; }point[10]; double mul(node1 a,node1 b,node1 c){ return (a.x-b.x)*(c.y-b.y)-(c.x-b.x)*(a.y-b.y); } bool check(node a,node b){ //下面这两行是判断是否存在共线问题（也可以说是判断共线），在这道题目当中是不加也不影响的 if(min(a.x1,a.x2)>max(b.x1,b.x2)||min(b.x1,b.x2)>max(a.x1,a.x2)) return false; if(min(a.y1,a.y2)>max(b.y1,b.y2)||min(b.y1,b.y2)>max(a.y1,a.y2)) return false; point[1].x=a.x1,point[1].y=a.y1; point[2].x=a.x2,point[2].y=a.y2; point[3].x=b.x1,point[3].y=b.y1; point[4].x=b.x2,point[4].y=b.y2; if(mul(point[1],point[3],point[4])*mul(point[2],point[3],point[4])<esp&& mul(point[3],point[1],point[2])*mul(point[4],point[1],point[2])<esp)//这里需要加一个esp，保证以下精度，要不然会wa的 return true; return false; } int main() { #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); #endif // ONLINE_JUDGE int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lf%lf%lf%lf",&num[i].x1,&num[i].y1,&num[i].x2,&num[i].y2); int ans=0; for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){ if(check(num[i],num[j])) ans++; } } printf("%d\n",ans); return 0; }