Question

计算两个矩形是否有相交部分，求C或C++源代码算法

已知如图两个矩形，他们的d（短边）是一样的，坐标点是d的中点。判断他们两者是否有相交部分，要考虑各种极端情况以确保算法正确。

请各位大神费心想想吧，最好就用到已有的这些条件，不要用大量的sin啊cos函数，越简单越好，我这个判断在整个程序里要反复调用的，多了会效率很慢。
好算法加分，拜托了啊！
不计算矩形的顶点坐标，算法复杂度要低，尽量运用我上面给出的这些条件不要另外计算获得条件。

Answer 1

//判断两条线段是否相交
bool judgep(point a, point b, point c, point d)
{
return a,b在cd直线两边 && c,d在ab直线两边;
}
//判断矩形相交
bool judger(rect r1, rect r2)
{
//通过(x1,y1),(x2,y2),d计算出矩形四个点
四条边每两条线段判断是否相交;
}

追问

不能用这个，这样的算法复杂度是8*8，而且计算矩形定点需要用到较多三角函数。

追答

8*8???
这个叫O(1)

追问

怎么不复杂？你判断每两条线是否相交，不就要套两循环么即4*4总共16次运用跨越算法，而且通过我所给的已知条件去算矩形的4个点本来就比较麻烦了，还用16次跨越算法判断，效率已经不满足我的要求了，我这个程序main里面要大概几亿次循环，每次循环要判断系统里约5000个这样矩形是否有相交的，这么来的话要跑到猴年马月啊。

Answer 2

我的思路需要用到解析几何，根据中点坐标和宽度d，得到矩形四个顶点的坐标：(L1,W1)(L2.W2)(L3,W3)(L4,L4),同理求出另一个矩形的四个顶点坐标：(l1,w1)(l2,w2)(l3,w3)(l4,w4)

矩形相交时，必须具备两个条件A.两个矩形顶点的横坐标范围有包含关系和相交关系
B.两个矩形顶点的纵坐标范围有包含和橡胶关系
其他情况一概不想交

Answer 3

楼主。你想多了，算法自己想啊

Answer 4

先把种类都罗列出来

Answer 5

acm里面很多的