nyoj-1016-德莱联盟(向量叉乘判断线段相交)
2024-09-02 19:39:08
叉乘的坐标表示:
A(X1,Y1), B(X2, Y2), C(XC,YC), D(XD, YD);
AB = (X2-X1, Y2-Y1);
CD = (XD-XC, YD-YC);
向量AB,CD的叉乘为:
AB*CD= (X2-X1)*(YD-YC)-(Y2-Y1)*(X2-X1);
例如两条直线,ab,cd来判断是否相交则根据
ans = (cd叉乘ca)*(cd叉乘bd)
如果ans大于等于0则相交,否则不相交。
下面是判断代码:
/*
Name:nyoj-1016-德莱联盟
Copyright:
Author:
Date: 2018/4/26 10:24:45
Description:
*/
#include <stdio.h>
#include <iostream>
using namespace std;
struct point{
double x,y;
};
int cross(point a,point b1,point b2){//求(b1-a) 和(b2-a) 的叉乘
double x1,y1,x2,y2;
x1=b1.x-a.x;
y1=b1.y-a.y;
x2=b2.x-a.x;
y2=b2.y-a.y;
return x1*y2-x2*y1;
}
int main()
{
int t;
cin>>t;
while(t--)
{
double ans1, ans2, ans3, ans4;
point A,B,C,D;
cin>>A.x>>A.y>>B.x>>B.y;//AB点的坐标
cin>>C.x>>C.y>>D.x>>D.y;//CD点的坐标
ans1=cross(A,C,D); //注意cross中向量的顺序,要相减的向量放在前面;向量CA和向量DA的叉乘
ans2=cross(B,C,D);
ans3=cross(C,A,B);
ans4=cross(D,A,B);
if(ans1*ans2< && ans3*ans4<){//判断点是否在同侧,如果AB在CD的同侧,不能相交
printf("Interseetion\n");
} else {
printf("Not Interseetion\n");
} }
}
最新文章
- oracle数据泵导入
- Android数据持久化技术 — — —SharedPreferences
- 浏览器兼容处理(HTML条件注释、CSSHack和JS识别)
- 变量声明提升 Vs. 函数声明提升
- bootstrap日期选择器-datetimepicker
- Hadoop入门进阶课程8--Hive介绍和安装部署
- 用C#编程的建议
- SQL Povit
- UVa 297 - Quadtrees
- 解决 android.view.ViewGroup$LayoutParams cannot be cast to android.widget.AbsListView$LayoutParams
- CentOS 6.7安装Java JDK
- 学习笔记 之--AJAX核心对象 XMLHttpRequest
- leetcode 3Sum Closest python
- EasyUI - DataGrid 组建 - [ 搜索功能 ]
- Java-List泛型的用处(能够使用传入泛型对象的方法)
- JavaScript ES6中export及export default的区别
- Tomcat修改端口号(7.0 version)
- hihoCoder编程练习赛72
- canvas(三) star- demo
- 服务端如何安全获取客户端请求IP地址