l*c
2 楼
前两周去onsite面的一家公司，其中一道题是（签了disclosure，不好全发出来）
1. How to represent a rectangle in a 2D plane? The rectangle can be rotated
by any angle.
2. How to determine if two given rectangle overlap with each other?
大概说思路+写代码用了半个小时，回来稍微整理了一下，下面是地址
http://blog.theliuy.com/determine-if-two-rotated-rectangles-ove
应该还有更好的办法，当时也只能想出来这么多了。。。
估计下周出结果，求bless，本人新手还不知道包子怎么给（也不知道自己有没有）…
…
1. How to represent a rectangle in a 2D plane? The rectangle can be rotated
by any angle.
2. How to determine if two given rectangle overlap with each other?
大概说思路+写代码用了半个小时，回来稍微整理了一下，下面是地址
http://blog.theliuy.com/determine-if-two-rotated-rectangles-ove
应该还有更好的办法，当时也只能想出来这么多了。。。
估计下周出结果，求bless，本人新手还不知道包子怎么给（也不知道自己有没有）…
…
s*l
3 楼
哈哈， re
【在 t*****e 的大作中提到】
: 本来就想做个二道饭子，现在都二十道饭子不止了
【在 t*****e 的大作中提到】
: 本来就想做个二道饭子，现在都二十道饭子不止了
f*s
4 楼
graphics的背景？
rotated
【在 l*****c 的大作中提到】
: 前两周去onsite面的一家公司，其中一道题是（签了disclosure，不好全发出来）
: 1. How to represent a rectangle in a 2D plane? The rectangle can be rotated
: by any angle.
: 2. How to determine if two given rectangle overlap with each other?
: 大概说思路+写代码用了半个小时，回来稍微整理了一下，下面是地址
: http://blog.theliuy.com/determine-if-two-rotated-rectangles-ove
: 应该还有更好的办法，当时也只能想出来这么多了。。。
: 估计下周出结果，求bless，本人新手还不知道包子怎么给（也不知道自己有没有）…
: …
rotated
【在 l*****c 的大作中提到】
: 前两周去onsite面的一家公司，其中一道题是（签了disclosure，不好全发出来）
: 1. How to represent a rectangle in a 2D plane? The rectangle can be rotated
: by any angle.
: 2. How to determine if two given rectangle overlap with each other?
: 大概说思路+写代码用了半个小时，回来稍微整理了一下，下面是地址
: http://blog.theliuy.com/determine-if-two-rotated-rectangles-ove
: 应该还有更好的办法，当时也只能想出来这么多了。。。
: 估计下周出结果，求bless，本人新手还不知道包子怎么给（也不知道自己有没有）…
: …
c*r
5 楼
护士至少是三道啊
【在 t*****e 的大作中提到】
: 本来就想做个二道饭子，现在都二十道饭子不止了
【在 t*****e 的大作中提到】
: 本来就想做个二道饭子，现在都二十道饭子不止了
l*c
6 楼
不是 面的都是kernel偏上一点的组……
【在 f******s 的大作中提到】
: graphics的背景？
:
: rotated
【在 f******s 的大作中提到】
: graphics的背景？
:
: rotated
t*e
7 楼
haha
【在 t*****e 的大作中提到】
: 本来就想做个二道饭子，现在都二十道饭子不止了
【在 t*****e 的大作中提到】
: 本来就想做个二道饭子，现在都二十道饭子不止了
f*s
8 楼
不是graphics考这个太偏了，是的话，考的又太简单。
【在 l*****c 的大作中提到】
: 不是 面的都是kernel偏上一点的组……
【在 l*****c 的大作中提到】
: 不是 面的都是kernel偏上一点的组……
D*9
9 楼
i am si dao
c*p
10 楼
mark
r*n
11 楼
"While, if the given rectangles are rotated by any angle, my solution is to
check the corners of each rectangle. If one of them is inside of another
rectangle, these two rectangles overlap. Otherwise, they are not."
不对吧，比如两个长方形组成十字架的形状，虽然没有任何一个角落在另外一个长方形
里面，但是这两个长方形仍然相交。
我觉得判定不相交比判定相交容易些：
求出长方形A的四条边的直线方程，这四条边组成两组平行线
用长方形B的四个角和A的两组平行线比较，如果存在一组平行线使得B的四个角都在其
同一侧（带入直线方程，符号一样），那么不相交。
否则互换A，B，然后再测试一下。
如果两次测试其中任何一次是“不相交”，那么A，B就不相交，否则A，B相交。
rotated
【在 l*****c 的大作中提到】
: 前两周去onsite面的一家公司，其中一道题是（签了disclosure，不好全发出来）
: 1. How to represent a rectangle in a 2D plane? The rectangle can be rotated
: by any angle.
: 2. How to determine if two given rectangle overlap with each other?
: 大概说思路+写代码用了半个小时，回来稍微整理了一下，下面是地址
: http://blog.theliuy.com/determine-if-two-rotated-rectangles-ove
: 应该还有更好的办法，当时也只能想出来这么多了。。。
: 估计下周出结果，求bless，本人新手还不知道包子怎么给（也不知道自己有没有）…
: …
check the corners of each rectangle. If one of them is inside of another
rectangle, these two rectangles overlap. Otherwise, they are not."
不对吧，比如两个长方形组成十字架的形状，虽然没有任何一个角落在另外一个长方形
里面，但是这两个长方形仍然相交。
我觉得判定不相交比判定相交容易些：
求出长方形A的四条边的直线方程，这四条边组成两组平行线
用长方形B的四个角和A的两组平行线比较，如果存在一组平行线使得B的四个角都在其
同一侧（带入直线方程，符号一样），那么不相交。
否则互换A，B，然后再测试一下。
如果两次测试其中任何一次是“不相交”，那么A，B就不相交，否则A，B相交。
rotated
【在 l*****c 的大作中提到】
: 前两周去onsite面的一家公司，其中一道题是（签了disclosure，不好全发出来）
: 1. How to represent a rectangle in a 2D plane? The rectangle can be rotated
: by any angle.
: 2. How to determine if two given rectangle overlap with each other?
: 大概说思路+写代码用了半个小时，回来稍微整理了一下，下面是地址
: http://blog.theliuy.com/determine-if-two-rotated-rectangles-ove
: 应该还有更好的办法，当时也只能想出来这么多了。。。
: 估计下周出结果，求bless，本人新手还不知道包子怎么给（也不知道自己有没有）…
: …
l*c
12 楼
哦对 忘了这个情况了……
to
【在 r*********n 的大作中提到】
: "While, if the given rectangles are rotated by any angle, my solution is to
: check the corners of each rectangle. If one of them is inside of another
: rectangle, these two rectangles overlap. Otherwise, they are not."
: 不对吧，比如两个长方形组成十字架的形状，虽然没有任何一个角落在另外一个长方形
: 里面，但是这两个长方形仍然相交。
: 我觉得判定不相交比判定相交容易些：
: 求出长方形A的四条边的直线方程，这四条边组成两组平行线
: 用长方形B的四个角和A的两组平行线比较，如果存在一组平行线使得B的四个角都在其
: 同一侧（带入直线方程，符号一样），那么不相交。
: 否则互换A，B，然后再测试一下。
to
【在 r*********n 的大作中提到】
: "While, if the given rectangles are rotated by any angle, my solution is to
: check the corners of each rectangle. If one of them is inside of another
: rectangle, these two rectangles overlap. Otherwise, they are not."
: 不对吧，比如两个长方形组成十字架的形状，虽然没有任何一个角落在另外一个长方形
: 里面，但是这两个长方形仍然相交。
: 我觉得判定不相交比判定相交容易些：
: 求出长方形A的四条边的直线方程，这四条边组成两组平行线
: 用长方形B的四个角和A的两组平行线比较，如果存在一组平行线使得B的四个角都在其
: 同一侧（带入直线方程，符号一样），那么不相交。
: 否则互换A，B，然后再测试一下。
f*y
13 楼
本人非码工，随便扯两句。
是我的话长方形的表示是一个中心点，任意两个相邻顶点。根据这个能求出长方形四条
边方程。如果两个长方形有重合那要么是边有相交（求线段交点是否在线段内），要么
是一个长方型完全被包在另一个内部。可以通过看中心点是否在另一个长方形内来判断
（检查定点到中心点距离小的那个长方形）。
是我的话长方形的表示是一个中心点，任意两个相邻顶点。根据这个能求出长方形四条
边方程。如果两个长方形有重合那要么是边有相交（求线段交点是否在线段内），要么
是一个长方型完全被包在另一个内部。可以通过看中心点是否在另一个长方形内来判断
（检查定点到中心点距离小的那个长方形）。
l*c
14 楼
非常感谢 感觉当时想的不够 所以给的解法也有不少问题
【在 f****y 的大作中提到】
: 本人非码工，随便扯两句。
: 是我的话长方形的表示是一个中心点，任意两个相邻顶点。根据这个能求出长方形四条
: 边方程。如果两个长方形有重合那要么是边有相交（求线段交点是否在线段内），要么
: 是一个长方型完全被包在另一个内部。可以通过看中心点是否在另一个长方形内来判断
: （检查定点到中心点距离小的那个长方形）。
【在 f****y 的大作中提到】
: 本人非码工，随便扯两句。
: 是我的话长方形的表示是一个中心点，任意两个相邻顶点。根据这个能求出长方形四条
: 边方程。如果两个长方形有重合那要么是边有相交（求线段交点是否在线段内），要么
: 是一个长方型完全被包在另一个内部。可以通过看中心点是否在另一个长方形内来判断
: （检查定点到中心点距离小的那个长方形）。
c*o
15 楼
看矩形a中的顶点是否在矩形b内
g*G
16 楼
EPI原题嘛
l*c
17 楼
当时的想法和你的很类似，但六楼提了一个特例。
【在 c******o 的大作中提到】
: 看矩形a中的顶点是否在矩形b内
【在 c******o 的大作中提到】
: 看矩形a中的顶点是否在矩形b内
c*o
18 楼
那把矩形按4个直线表示。
矩形a的4个顶点都应该在矩形b的4个直线的同一侧
【在 l*****c 的大作中提到】
: 当时的想法和你的很类似，但六楼提了一个特例。
矩形a的4个顶点都应该在矩形b的4个直线的同一侧
【在 l*****c 的大作中提到】
: 当时的想法和你的很类似，但六楼提了一个特例。
相关阅读
【求助】怎样回复这个recruiter?About Palantir Technologies请帮着分析G家状况，顺便求bless都老大不小了 转专业 还来得及么？请教在H1B未激活时用B1/B2入境的问题明天出发去onsite, 求blesscap-exempt H1B普通速度办理一般要多长时间?痛苦得等offer在线问个问题SQL Server 最近有关讲座征求意见 (转载)请教办绿卡的前辈们。。电话面试真心不好搞啊问一个 String array sorting 的题。拿到Facebook,Apple,Google的OfferH1B transfer RFEfacebook 最近还在招人么我必须得开始找工作了CFD Job谁知道google投简历的间隔时间？找min cut的解有什么简单的算法吗？ (转载)