s*******a 发帖数: 4166 | 1 刚才在等飞机,做了点brain teaser打发时间,后来自己想到这个问题:
2个给定的三角形,如何判断一个能否被另一个三角形覆盖?不知道有没有比较初等的
方法,想了半天没想出来。 |
C********n 发帖数: 6682 | 2 三边小于最短边+最长高小于最短高应该能确保吧
必要条件没想出来
【在 s*******a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 刚才在等飞机,做了点brain teaser打发时间,后来自己想到这个问题: : 2个给定的三角形,如何判断一个能否被另一个三角形覆盖?不知道有没有比较初等的 : 方法,想了半天没想出来。
|
s*******a 发帖数: 4166 | 3 当然问的是必要条件啊......
【在 C********n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 三边小于最短边+最长高小于最短高应该能确保吧 : 必要条件没想出来
|
s*******a 发帖数: 4166 | 4 如果是两个平行四边形的话非常简单
我一开始的想法是,每个三角形都可以生成3个不同的平行四边形,如果能证明三角形
覆盖与其中某一对平行四边形能覆盖是等价的,那就行了。不过我也没想出一个简单的
证明,也没想出反例。
【在 C********n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 三边小于最短边+最长高小于最短高应该能确保吧 : 必要条件没想出来
|
s*****a 发帖数: 353 | 5 完全覆盖的话,难道不就是验证第二个的顶点是否全在第一个内? |
C********n 发帖数: 6682 | 6 ....
是
但是第二个的坐标不是固定的啊,可以任意旋转平移啊
【在 s*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 完全覆盖的话,难道不就是验证第二个的顶点是否全在第一个内?
|
s*****V 发帖数: 21731 | 7 如果一个可以覆盖另外一个,则一定能找到一种情形,
当双方一个顶点重合,然后三角形1的该顶点角小于等于三角形2对应角度,两边也小于
等于三角形2的对应两边。
如果知道两个三角形的三点坐标,很好判断吧,把几种情形穷举一下就可以,也就是把
。3X3 9中情形。
说白了就是把两三角形一个顶点对住,然后旋转到一起比较一下。当然这是笨方法,
【在 s*******a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 刚才在等飞机,做了点brain teaser打发时间,后来自己想到这个问题: : 2个给定的三角形,如何判断一个能否被另一个三角形覆盖?不知道有没有比较初等的 : 方法,想了半天没想出来。
|
s*******a 发帖数: 4166 | 8 貌似是对的,但是怎么证明你说的第一个前提一定是对的
【在 s*****V 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 如果一个可以覆盖另外一个,则一定能找到一种情形, : 当双方一个顶点重合,然后三角形1的该顶点角小于等于三角形2对应角度,两边也小于 : 等于三角形2的对应两边。 : 如果知道两个三角形的三点坐标,很好判断吧,把几种情形穷举一下就可以,也就是把 : 。3X3 9中情形。 : 说白了就是把两三角形一个顶点对住,然后旋转到一起比较一下。当然这是笨方法,
|
s*****V 发帖数: 21731 | 9 三个点坐标都知道的时候很好算,两个向量之间的夹角。
【在 s*******a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 貌似是对的,但是怎么证明你说的第一个前提一定是对的
|
s**e 发帖数: 1834 | 10 这个说法是错的,顶点可重合,但对应边不一定小。
反例:
三角形1顶点: (0,1), (2,0),(3,0)
三角形2顶点:(0,1),(1,0),(4,0)
【在 s*****V 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 如果一个可以覆盖另外一个,则一定能找到一种情形, : 当双方一个顶点重合,然后三角形1的该顶点角小于等于三角形2对应角度,两边也小于 : 等于三角形2的对应两边。 : 如果知道两个三角形的三点坐标,很好判断吧,把几种情形穷举一下就可以,也就是把 : 。3X3 9中情形。 : 说白了就是把两三角形一个顶点对住,然后旋转到一起比较一下。当然这是笨方法,
|
|
|
s*****V 发帖数: 21731 | 11 你是对的,我的办法不行,当然修改一下还是可以的,
转一圈,如果两个顶点都不能TOUCH 第三条边,肯定可以。
如果有交点,转到交点位置,看看另外一个顶点在哪里。
写CODE没问题,可是方法不直观
【在 s**e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个说法是错的,顶点可重合,但对应边不一定小。 : 反例: : 三角形1顶点: (0,1), (2,0),(3,0) : 三角形2顶点:(0,1),(1,0),(4,0)
|
s**e 发帖数: 1834 | 12 我觉得“双方一个顶点可重合”应该是对的,但需证明,
而且证明未必trivial.
【在 s*****V 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你是对的,我的办法不行,当然修改一下还是可以的, : 转一圈,如果两个顶点都不能TOUCH 第三条边,肯定可以。 : 如果有交点,转到交点位置,看看另外一个顶点在哪里。 : 写CODE没问题,可是方法不直观
|
s**e 发帖数: 1834 | 13 非常有趣的题目,是自己构造出的吗?
以下假设小三角形(A'B'C')可被大三角形(ABC)覆盖。
在此假设下,我先证明一个局部结果。
如果大家有兴趣再一步步来。
结论1: 存在一种覆盖使大小三角形有一个顶点重合。
在不改变题目性质下,我们先将ABC成比例缩到最小,
使得再小就无法完成覆盖A'B'C'.
在此假设下,我们来证明一个更强的结论。
结论2: 任一种覆盖都一定会有一个顶点重合。
如果证明了2,自然就证明了1.
大三角形的边记为a,b,c.
证明:
首先对任意覆盖,大三角形的三边一定都被碰到,
否则大三角形可继续缩小,与先前假设矛盾。
接下用反证法。如果没有一个顶点重合,那么A'B'C'的
每一个顶点都严格在ABC的一边的内部(不含在端点上)。
假设A'在BC上,B'在AC上,C'在AB上。
现在过A'作BC垂线,过B'作AC垂线,两线交与D。
我们现证明DC'一定与AB垂直。
否则以D为旋转中心来旋转A'B'C'一个小角度x,
A'离开BC距离为O(x^2), B'离开AC距离也为O(x^2),
而C'离开AB距离为O(x)。
适当选取x的正负,可继续缩小ABC比例O(x)
(可能还会有平移,但不需要旋转),使得仍可形成覆盖。
这与先前假设矛盾,所以DC'一定与AB垂直,
并且在旋转下C'离开AB距离也为O(x^2)。
仍以D为旋转中心来旋转A'B'C'一个小角度x,
想象一下如果ABC三边都黏在了A'B'C'定点上,
跟随变动但保持每边的方向不变,那么ABC
每一边都以”同样的“比例(和x有关,O(x^2)量级)
向D点靠拢。因此ABC可继续缩小同时保持覆盖,
这样就又矛盾了。
最后结论:大小三角形必有一点重合。
【在 s*******a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 刚才在等飞机,做了点brain teaser打发时间,后来自己想到这个问题: : 2个给定的三角形,如何判断一个能否被另一个三角形覆盖?不知道有没有比较初等的 : 方法,想了半天没想出来。
|
s*******a 发帖数: 4166 | 14 是我昨天等飞机的时候想到的,其实可以推广到凸多边形或者高维单形。
另外你的证明我大概follow了一下,你说过A' 做BC的垂线,B' 做AC的垂线相交与D,
然后claim DC' 肯定垂直与AB,否则可以通过D旋转A'B'C'让他完全在ABC内部,我
画了一下貌似不大对啊,或者是证明里有typo?
因为是三角形,可以先假设ABC是正三角形的,你的大思路应该是对的,就假设A',B',C'
分别落在ABC三边上,然后讨论若干情况,但我刚才画了一下,如果A'B'C'是一个很
钝的三角形(比如A'在BC边上,然后B'C' 特别靠近BC边),很容易画出一个情况使得无论
怎么旋转都会转出ABC,这种情况必须翻转A'B'C'然后再继续旋转。
没想到有同学还真认真想,呵呵。这题看来有点高中奥数的水平了,如果有比较简洁初等
的证明,我们可以给IMO or CMO推荐一下,但首先得保证有个初等证明才好。
【在 s**e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 非常有趣的题目,是自己构造出的吗? : 以下假设小三角形(A'B'C')可被大三角形(ABC)覆盖。 : 在此假设下,我先证明一个局部结果。 : 如果大家有兴趣再一步步来。 : 结论1: 存在一种覆盖使大小三角形有一个顶点重合。 : 在不改变题目性质下,我们先将ABC成比例缩到最小, : 使得再小就无法完成覆盖A'B'C'. : 在此假设下,我们来证明一个更强的结论。 : 结论2: 任一种覆盖都一定会有一个顶点重合。 : 如果证明了2,自然就证明了1.
|
s**e 发帖数: 1834 | 15 我没有说转的时候一定转到ABC内部。
如果固定ABC不动,A',B'和C'有可能转到ABC外部。
但我这里让ABC跟着A'B'C'动。
先说如果DC' 不垂直于AB这种情况。
让ABC黏在A'B'C'顶点上随着A'B'C'旋转而
平行移动(边长可变)。
我们可以选择旋转角度x
的方向而使AB朝着或背着D的方向运动,变化率为O(x)。
BC和AC都朝着D的方向运动,但变化率仅为O(x^2)。
因此AB的移动决定了ABC变大或变小。
我们总可以选一个AB的方向(朝着或背着D),使得ABC变小。
以上证明不需用到ABC和A'B'C'的角度是钝角还是锐角。
,C'
无论
初等
【在 s*******a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 是我昨天等飞机的时候想到的,其实可以推广到凸多边形或者高维单形。 : 另外你的证明我大概follow了一下,你说过A' 做BC的垂线,B' 做AC的垂线相交与D, : 然后claim DC' 肯定垂直与AB,否则可以通过D旋转A'B'C'让他完全在ABC内部,我 : 画了一下貌似不大对啊,或者是证明里有typo? : 因为是三角形,可以先假设ABC是正三角形的,你的大思路应该是对的,就假设A',B',C' : 分别落在ABC三边上,然后讨论若干情况,但我刚才画了一下,如果A'B'C'是一个很 : 钝的三角形(比如A'在BC边上,然后B'C' 特别靠近BC边),很容易画出一个情况使得无论 : 怎么旋转都会转出ABC,这种情况必须翻转A'B'C'然后再继续旋转。 : 没想到有同学还真认真想,呵呵。这题看来有点高中奥数的水平了,如果有比较简洁初等 : 的证明,我们可以给IMO or CMO推荐一下,但首先得保证有个初等证明才好。
|
l***o 发帖数: 7937 | 16 将两个三角形的重心重合在一起会不会更简单?没仔细想,只是直觉会更简单一些。
【在 s**e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我没有说转的时候一定转到ABC内部。 : 如果固定ABC不动,A',B'和C'有可能转到ABC外部。 : 但我这里让ABC跟着A'B'C'动。 : 先说如果DC' 不垂直于AB这种情况。 : 让ABC黏在A'B'C'顶点上随着A'B'C'旋转而 : 平行移动(边长可变)。 : 我们可以选择旋转角度x : 的方向而使AB朝着或背着D的方向运动,变化率为O(x)。 : BC和AC都朝着D的方向运动,但变化率仅为O(x^2)。 : 因此AB的移动决定了ABC变大或变小。
|
s**e 发帖数: 1834 | 17 因为重心只涉及平面的线性空间的性质,因而和度量,例如长度和角度,
没有直接关系(虽说和距离平方和有关,但和单个的距离确实没什么关系)。
而这个问题可以旋转三角形(旋转就是保距变幻,也保角),和长度与角度
都有关系。所以我很怀疑考虑重心会使题目变简单。
【在 l***o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 将两个三角形的重心重合在一起会不会更简单?没仔细想,只是直觉会更简单一些。
|
q********e 发帖数: 1255 | 18 不行
想象一个三角形,无钝角,底边最长,放在那里,
在此三角形 内 以同样底边构造一个矮三角形,
such that 稍微一动,矮的就跑出来了,以至于重心不能重合。
结论:如果让重心重合,会漏掉解。
【在 l***o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 将两个三角形的重心重合在一起会不会更简单?没仔细想,只是直觉会更简单一些。
|
l***o 发帖数: 7937 | 19 别的心呢?例如内接圆圆心?
【在 s**e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 因为重心只涉及平面的线性空间的性质,因而和度量,例如长度和角度, : 没有直接关系(虽说和距离平方和有关,但和单个的距离确实没什么关系)。 : 而这个问题可以旋转三角形(旋转就是保距变幻,也保角),和长度与角度 : 都有关系。所以我很怀疑考虑重心会使题目变简单。
|
q********e 发帖数: 1255 | 20 呵呵,有无钝角无关系
接着soze的帖子,我猜测如果A cover B,那么让三边按长度对应,
然后让最长边重合,然后平移,应该也有一个covering.
不知道能否证明。
【在 q********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不行 : 想象一个三角形,无钝角,底边最长,放在那里, : 在此三角形 内 以同样底边构造一个矮三角形, : such that 稍微一动,矮的就跑出来了,以至于重心不能重合。 : 结论:如果让重心重合,会漏掉解。
|
|
|
q********e 发帖数: 1255 | 21 no, same reasoning as above
【在 l***o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 别的心呢?例如内接圆圆心?
|
s**e 发帖数: 1834 | 22 呵呵,这个不行。
让大三角形ABC是一个等腰锐角三角形,底边BC为最长边。
小三取顶点A,B,和AC上非常靠近C的一点。
那么小三和大三最长边没法重合。这里顶角是“锐角”很重要。
【在 q********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 呵呵,有无钝角无关系 : 接着soze的帖子,我猜测如果A cover B,那么让三边按长度对应, : 然后让最长边重合,然后平移,应该也有一个covering. : 不知道能否证明。
|
q********e 发帖数: 1255 | 23 make sense, 3x
【在 s**e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 呵呵,这个不行。 : 让大三角形ABC是一个等腰锐角三角形,底边BC为最长边。 : 小三取顶点A,B,和AC上非常靠近C的一点。 : 那么小三和大三最长边没法重合。这里顶角是“锐角”很重要。
|
l***o 发帖数: 7937 | 24 对于圆,椭圆,正三角形,直角三角形等特殊情况,显然将中心或重心重合起来更简单
一点。对于三角形,我根据直觉推断将某个心先重合起来做判断更简单一点。甚至可以
推导出一个判断公式。
【在 q********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : no, same reasoning as above
|
f****p 发帖数: 18483 | 25 这个题很好解。
本质上三角形可以有角边角或者边角边来确定。这就是两个三角形恒等的判别法。
具体的定理论述我就不给了,不过我可以把想法说下。
假设有两个三角形ABC,和XYZ。A、B、C、X、Y、Z都是顶点。AB和XY分别是两个三角形
的最长边。
首先,将A和X重叠,AB和XY同方向,这个是个基点。
这样就有两种情况: (1)|AB| = |XY| (2) |AB| < |XY|
(1)比较容易,因为 角CAB 角ZXY 的情况可以用它们的cos来指导,分为一正一负,
两个全正,和两个全负三种。然后再比较值
(2)稍微麻烦点,因为情况得用cos值和|CA|、|ZX|来确定,但是也不难,因为你用那
个A到BC以及X到YZ的距离还有cos值就可以判断。
楼上用什么重心呀、内接圆之类的都在绕,都不可能是必要的。上面这个方法肯定是充
分和必要的。你自己去写成定理形式就行了。 |
q********e 发帖数: 1255 | 26 貌似你的arguments基于我上边被soze证伪的一个错误猜想
其实soze已经给出了答案,顶点依次订一起,转转看,3*3=9次。
然后镜像下,再转。总共转2*9=18次即可。
【在 f****p 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个题很好解。 : 本质上三角形可以有角边角或者边角边来确定。这就是两个三角形恒等的判别法。 : 具体的定理论述我就不给了,不过我可以把想法说下。 : 假设有两个三角形ABC,和XYZ。A、B、C、X、Y、Z都是顶点。AB和XY分别是两个三角形 : 的最长边。 : 首先,将A和X重叠,AB和XY同方向,这个是个基点。 : 这样就有两种情况: (1)|AB| = |XY| (2) |AB| < |XY| : (1)比较容易,因为 角CAB 角ZXY 的情况可以用它们的cos来指导,分为一正一负, : 两个全正,和两个全负三种。然后再比较值 : (2)稍微麻烦点,因为情况得用cos值和|CA|、|ZX|来确定,但是也不难,因为你用那
|
s**e 发帖数: 1834 | 27 现在接着part 1来补全余下证明,相对简单得多,
没太多技巧。
仍假设ABC(大三角形)再缩小
就不能覆盖A'B'C'(小三角形)了。
根据之前的结论1,2,现假设A与A'重叠,
且ABC与A'B'C'同向。
因为ABC不能再缩小,所以覆盖只能有以下几种可能。
(1)B'与B重叠
(2)B'在AB内部,C'在BC内部
(3)B'与C'都在BC内部
(4)(类似(2)),C'在AC内部,B'在BC内部
(5)C'与C重叠
现在取消ABC不能再缩小去覆盖A'B'C'这个限制,
从新解读以上五条,我们得到:
(1') AB>=A'B'; angle A >= angle A'; angle B >= angle B'.
(2') AB>=A'B'; angle A >= angle A';
AB*sin(B) >= A'C'*sin(A'+B).
(3') BC边的高 >= B'C'边的高; angle B <= angle B';
angle C <= angle C';
(4') AC>=A'C'; angle A >= angle A';
AC*sin(C) >= A'B'*sin(A'+C).
(5') AC>=A'C'; angle A >= angle A'; angle C >= angle C'.
所以在A与A'重合且ABC与A'B'C'同向的前提下,
ABC覆盖A'B'C'的充要条件是满足(1')...(5')
五条之一既可。
考虑到A'B'C'和ABC可以由其它顶点来重合,而且A'B'C'可翻转。
把这些都考虑进去既可。
其中(1')(5')和(3')可被大大简化为以下两条:
(1'')ABC某一边>=A'B'C'某一边,且对应相邻角是ABC的大。
(3'')ABC某一边的高>=A'B'C'某一边的高,且对应相邻角是A'B'C'的大。
大家若有兴趣可以试着简化一下(2')和(4')。
【在 s*******a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 刚才在等飞机,做了点brain teaser打发时间,后来自己想到这个问题: : 2个给定的三角形,如何判断一个能否被另一个三角形覆盖?不知道有没有比较初等的 : 方法,想了半天没想出来。
|
f*****s 发帖数: 95 | 28 妙!不过三垂线交于三角形外一点D的情形要说明。假定D在BC边外,以D为中心旋转A'B
'C'对ABC的影响大概是 DBC面积 - (DAB面积 + DBC面积 )〈 0. 所以ABC面积会缩
小。ABC换成任意凸多边形貌似也成立,也就是说 the only way to lock a triangle
is to corner it. 有趣!这个结论显见对四边形不成立。但对四面体呢?
【在 s**e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 非常有趣的题目,是自己构造出的吗? : 以下假设小三角形(A'B'C')可被大三角形(ABC)覆盖。 : 在此假设下,我先证明一个局部结果。 : 如果大家有兴趣再一步步来。 : 结论1: 存在一种覆盖使大小三角形有一个顶点重合。 : 在不改变题目性质下,我们先将ABC成比例缩到最小, : 使得再小就无法完成覆盖A'B'C'. : 在此假设下,我们来证明一个更强的结论。 : 结论2: 任一种覆盖都一定会有一个顶点重合。 : 如果证明了2,自然就证明了1.
|
s**e 发帖数: 1834 | 29 如果用有向面积的话,D在里还是外就关系不大了。
高维不好说,因为每个顶点的立体角都怪怪的,
不是小的角就一定能放的进去。
好多看似简单的三角形问题刚到三维就不对了。
例如说四面体就没有垂心。
'B
triangle
【在 f*****s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 妙!不过三垂线交于三角形外一点D的情形要说明。假定D在BC边外,以D为中心旋转A'B : 'C'对ABC的影响大概是 DBC面积 - (DAB面积 + DBC面积 )〈 0. 所以ABC面积会缩 : 小。ABC换成任意凸多边形貌似也成立,也就是说 the only way to lock a triangle : is to corner it. 有趣!这个结论显见对四边形不成立。但对四面体呢?
|
f*****s 发帖数: 95 | 30 n 维空间里的运动有 n(n+1)/2 个自由度,直观的,限制住这 n(n+1)/2 自由度至少需
要 n(n+1)/2+1个面,所以有如下猜测:
任何 n 维空间中 n(n+1)/2 个顶点的凸多面体不可能被 n(n+1)/2 个平面 lock (不能
local的
移动), 并使得每个顶点在面的内部(即任一顶点不在任两个面的交上)。n=1
trivially true. 如上证的是 n=2 的情形。 |
|
|
y**k 发帖数: 222 | 31 不是要抢包子,不过上面 soze 的方法似乎可以大大简化。
引理: 如果A'在BC上, B' 在 AC内部, C' 在 AB 内部(即 B', C' 不与三角形 ABC
任何一顶点重合), 那么可以找到一个与A'B'C' 相似的更大的三角形 A'B''C''被ABC
覆盖。
证明: 不失一般性, 可以假定直线 A'B' 跟 AC 不重合, 那么可以使用一个线性变
换在所有点上, 使得 A'B' 跟 AC 垂直。让三角形 A'B'C' 沿着A'做顺时针或逆时针
小幅旋转, 一定可以使B' 和 C' 落在三角形 ABC 内部。
下略。 |
s**e 发帖数: 1834 | 32 这个线性变换(使得 A'B' 跟 AC 垂直)不是保距变换。
不能保持旋转的性质。
ABC
【在 y**k 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不是要抢包子,不过上面 soze 的方法似乎可以大大简化。 : 引理: 如果A'在BC上, B' 在 AC内部, C' 在 AB 内部(即 B', C' 不与三角形 ABC : 任何一顶点重合), 那么可以找到一个与A'B'C' 相似的更大的三角形 A'B''C''被ABC : 覆盖。 : 证明: 不失一般性, 可以假定直线 A'B' 跟 AC 不重合, 那么可以使用一个线性变 : 换在所有点上, 使得 A'B' 跟 AC 垂直。让三角形 A'B'C' 沿着A'做顺时针或逆时针 : 小幅旋转, 一定可以使B' 和 C' 落在三角形 ABC 内部。 : 下略。
|
y**k 发帖数: 222 | 33 确实不是, 也不需要是。
【在 s**e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个线性变换(使得 A'B' 跟 AC 垂直)不是保距变换。 : 不能保持旋转的性质。 : : ABC
|
s**e 发帖数: 1834 | 34 可能我还没有完全理解你的意思。
这是我的粗浅理解。先来一个线性变幻T,
然后在小三角形上再来一个旋转S,
然后变换后的小三角形 ST(small)
就转到变换后的大三角形 T(big) 里了。
再来一个线性逆变幻 T^(-1),
就可得到 T^(-1)ST(small) 在大三角形里。
但 T^(-1)ST(small)已不是最初的
小三角形了。
【在 y**k 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 确实不是, 也不需要是。
|
y**k 发帖数: 222 | 35 嗯, 你说得对。
【在 s**e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 可能我还没有完全理解你的意思。 : 这是我的粗浅理解。先来一个线性变幻T, : 然后在小三角形上再来一个旋转S, : 然后变换后的小三角形 ST(small) : 就转到变换后的大三角形 T(big) 里了。 : 再来一个线性逆变幻 T^(-1), : 就可得到 T^(-1)ST(small) 在大三角形里。 : 但 T^(-1)ST(small)已不是最初的 : 小三角形了。
|
c***s 发帖数: 15 | 36 好像是一个组合问题:假设两三角形ABC,abc,面积分别为S和s。不失一般性,令S>=s
, 要求ABC覆盖abc,我们寻找ABC的相似三角形ABC',最小面积S',使得顶角A'和a重合
并且底边重合,则 S' = (cot B + cot C)/(cot b + cot c)s并且要求B<= b并且C<=c.
这就要求我们遍历所有的组合{(X,x)(Y,y)} = {(X <= x, Y <= y)| X,Y \in ABC, x,
y \in abc },可由二分图的匹配给出。所以ABC覆盖abc的充要条件是 S >= s min_{{(
X,x)(Y,y)}} r((X,x)(Y,y)), 这里r((X,x)(Y,y)) = (cot X + cot Y)/(cot x + cot
y). |
c***s 发帖数: 15 | 37 哦,需要修正一下
如果BC,bc不能保证B <= b & C <= c或者 B <= c & C <= b,那么最优的ABC'有一个
侧边
和abc重合(非底边),不失一般性令 b > B >= C >= c (顶角A>= a),则A'C' = ac
S' = (cot a + cot c)/(cot A + cot C) s,这个对应一条边完全重合,而b >= B的情
况。
所以r((X, Y, x ,y)) = (cot X + cot Y)/(cot x + cot y) if X <= x & Y <= y
or = (cot x + cot y)/(cot X + cot Y), if X >= x & Y >= y.
config(X,Y, x, y)从(A,B,C)和(a,b,c)各取两个共有9种,同时要求不能最大和最小值
来自于同一个三角形。
S >= s min_{(X,Y,x,y)} r((X,Y, x, y), where r(X, Y, x, y) = max
((cot X + cot Y)/(cot x + cot y), (cot x + cot y)/(cot X + cot X))
=s
c.
cot
【在 c***s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 好像是一个组合问题:假设两三角形ABC,abc,面积分别为S和s。不失一般性,令S>=s : , 要求ABC覆盖abc,我们寻找ABC的相似三角形ABC',最小面积S',使得顶角A'和a重合 : 并且底边重合,则 S' = (cot B + cot C)/(cot b + cot c)s并且要求B<= b并且C<=c. : 这就要求我们遍历所有的组合{(X,x)(Y,y)} = {(X <= x, Y <= y)| X,Y \in ABC, x, : y \in abc },可由二分图的匹配给出。所以ABC覆盖abc的充要条件是 S >= s min_{{( : X,x)(Y,y)}} r((X,x)(Y,y)), 这里r((X,x)(Y,y)) = (cot X + cot Y)/(cot x + cot : y).
|
s*****V 发帖数: 21731 | 38 有一个猜想,如果一个三角形的三条高A都比另外一个三角形三条高A'不重复的都大,
则A可以覆盖A。应该是必要条件,不知道充分不充分。 |
c*******1 发帖数: 240 | 39 the set
W_a,b,c = {x,y,z in R3 : triangle with side length x,y,z can be covered by
triangle of side length a,b,c}
is a convex hyperbolic polyhedron with some flat faces. |
i*****s 发帖数: 4596 | 40 你的证明没写完啊,DC'垂直于AB这种情况呢?这时候三边的距离变化都是O(x^2),如
果D在三角形之外的话,三边与D的距离不一定都是往一个方向变,你说得清ABC是变大
还是变小么。
事实上你的猜想可能是正确的,但你并没有完全证明出来。
【在 s**e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我没有说转的时候一定转到ABC内部。 : 如果固定ABC不动,A',B'和C'有可能转到ABC外部。 : 但我这里让ABC跟着A'B'C'动。 : 先说如果DC' 不垂直于AB这种情况。 : 让ABC黏在A'B'C'顶点上随着A'B'C'旋转而 : 平行移动(边长可变)。 : 我们可以选择旋转角度x : 的方向而使AB朝着或背着D的方向运动,变化率为O(x)。 : BC和AC都朝着D的方向运动,但变化率仅为O(x^2)。 : 因此AB的移动决定了ABC变大或变小。
|
|
|
s**e 发帖数: 1834 | 41 呵呵,我应该是说了。
见“- Part 1”贴。
“那么ABC
每一边都以”同样的“比例(和x有关,O(x^2)量级)
向D点靠拢。”
这时无论x是正还是负,ABC三边都以cos(x)
的比例向D点“靠拢”。因此ABC也以cos(x)
的比例在缩小,而这是和D点在ABC内还是外
是没有关系的。
当然如果D在ABC外,那么ABC不是直接向内部
缩小,看起来好像没有D在ABC内部那么直观。
【在 i*****s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你的证明没写完啊,DC'垂直于AB这种情况呢?这时候三边的距离变化都是O(x^2),如 : 果D在三角形之外的话,三边与D的距离不一定都是往一个方向变,你说得清ABC是变大 : 还是变小么。 : 事实上你的猜想可能是正确的,但你并没有完全证明出来。
|
i*****s 发帖数: 4596 | 42 是我没仔细想,你是对的。
【在 s**e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 呵呵,我应该是说了。 : 见“- Part 1”贴。 : “那么ABC : 每一边都以”同样的“比例(和x有关,O(x^2)量级) : 向D点靠拢。” : 这时无论x是正还是负,ABC三边都以cos(x) : 的比例向D点“靠拢”。因此ABC也以cos(x) : 的比例在缩小,而这是和D点在ABC内还是外 : 是没有关系的。 : 当然如果D在ABC外,那么ABC不是直接向内部
|
s**e 发帖数: 1834 | 43 谢谢你仔细帮助校对。
【在 i*****s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 是我没仔细想,你是对的。
|
s***5 发帖数: 203 | 44 三角形ABC可以覆盖三角形DEF的充要条件:点D,E,F在三角形ABC内部(含在边界的情
形)。
证明非常简单:
必要性:如果三角形ABC可以覆盖三角形DEF,当然点D,E,F在三角形ABC内部(含在边
界的情形)
充分性:如果点D,E,F在三角形ABC内部(含在边界的情形),
1)由于三角形ABC是凸的,可知线段DE,EF,DF,都在三角形ABC内部,
2)对于三角形DEF内部不在边界上的点X,延长DX,就可以交于线段EF,把交点叫Y吧,
由1)知Y也在三角形ABC内部,这样点D和Y都在三角形ABC内部,由于三角形ABC是凸的
,线段DY在三角形ABC内部,当然线段DY上的点X在三角形ABC内部。(含在边界的情形)
图不好,见笑了。
A
********************* B
* F Y E *
* 。。。。。。。 *
* 。X 。 。 *
* 。 。 。 *
* 。 *
* D *
*
C
【在 s*******a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 刚才在等飞机,做了点brain teaser打发时间,后来自己想到这个问题: : 2个给定的三角形,如何判断一个能否被另一个三角形覆盖?不知道有没有比较初等的 : 方法,想了半天没想出来。
|
s*****j 发帖数: 6435 | 45 我觉得见笑的不是图.
形)
【在 s***5 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 三角形ABC可以覆盖三角形DEF的充要条件:点D,E,F在三角形ABC内部(含在边界的情 : 形)。 : 证明非常简单: : 必要性:如果三角形ABC可以覆盖三角形DEF,当然点D,E,F在三角形ABC内部(含在边 : 界的情形) : 充分性:如果点D,E,F在三角形ABC内部(含在边界的情形), : 1)由于三角形ABC是凸的,可知线段DE,EF,DF,都在三角形ABC内部, : 2)对于三角形DEF内部不在边界上的点X,延长DX,就可以交于线段EF,把交点叫Y吧, : 由1)知Y也在三角形ABC内部,这样点D和Y都在三角形ABC内部,由于三角形ABC是凸的 : ,线段DY在三角形ABC内部,当然线段DY上的点X在三角形ABC内部。(含在边界的情形)
|
s***5 发帖数: 203 | 46 再进一步,三角形ABC,坐标A(a1,a2), B(b1,b2), C(c1,c2), 以及另一个点D坐标(d1,
d2),D在三角形ABC内部(含在边界的情 形)的充要条件是?
答案:
max(角DCA,角DCB) 《= 角BCA 且
max(角DAC,角DAB) 《= 角ACB 且
max(角DBC,角DBA) 《= 角ABC
A********************* B
* *
* D *
* 。 *
* *
* *
* *
*
C
实际计算,可以用计算角的余铉cos,因为cos是在(0,pi)单调递减的,也就是:
min(cos(角DCA),cos(角DCB)) >= cos(角BCA) 且
min(cos(角DAC),cos(角DAB)) >= cos(角ACB) 且
min(cos(角DBC),cos(角DBA)) >= cos(角ABC)
cos(角DCA)=〈CD,CA〉/ (||CD|| * ||CA||)
其中〈CD,CA〉是向量CD和CA的内积,||CD|| 和 ||CA||是向量CD和CA的模,
〈CD,CA〉=(d1-c1)*(a1-c1) +(d2-c2)*(a2-c2)
||CD|| =sqrt( ( d1-c1 )*(d1-c1) + ( d2-c2 )*(d2-c2))
||CA|| =sqrt( ( a1-c1 )*(a1-c1) + ( a2-c2 )*(a2-c2))
其余类推。
同样,对点E, F,就可以解决ABC可以覆盖三角形DEF的充要条件。
把公式都写出来就太苯了,编程序要清爽些。
顺便说一下,应该先验证ABC三点不在一条线上,然后再用这个算法。
形)
【在 s***5 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 三角形ABC可以覆盖三角形DEF的充要条件:点D,E,F在三角形ABC内部(含在边界的情 : 形)。 : 证明非常简单: : 必要性:如果三角形ABC可以覆盖三角形DEF,当然点D,E,F在三角形ABC内部(含在边 : 界的情形) : 充分性:如果点D,E,F在三角形ABC内部(含在边界的情形), : 1)由于三角形ABC是凸的,可知线段DE,EF,DF,都在三角形ABC内部, : 2)对于三角形DEF内部不在边界上的点X,延长DX,就可以交于线段EF,把交点叫Y吧, : 由1)知Y也在三角形ABC内部,这样点D和Y都在三角形ABC内部,由于三角形ABC是凸的 : ,线段DY在三角形ABC内部,当然线段DY上的点X在三角形ABC内部。(含在边界的情形)
|
s***5 发帖数: 203 | 47 请兄台明示。
【在 s*****j 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我觉得见笑的不是图. : : 形)
|
l***o 发帖数: 7937 | 48 充要条件是DEF经过适当平移和旋转后,D,E,F全在ABC内部或边界上。或者说可以找到
一个平移和旋转,使得D,E,F三点在ABC内部或边界上。
形)
【在 s***5 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 三角形ABC可以覆盖三角形DEF的充要条件:点D,E,F在三角形ABC内部(含在边界的情 : 形)。 : 证明非常简单: : 必要性:如果三角形ABC可以覆盖三角形DEF,当然点D,E,F在三角形ABC内部(含在边 : 界的情形) : 充分性:如果点D,E,F在三角形ABC内部(含在边界的情形), : 1)由于三角形ABC是凸的,可知线段DE,EF,DF,都在三角形ABC内部, : 2)对于三角形DEF内部不在边界上的点X,延长DX,就可以交于线段EF,把交点叫Y吧, : 由1)知Y也在三角形ABC内部,这样点D和Y都在三角形ABC内部,由于三角形ABC是凸的 : ,线段DY在三角形ABC内部,当然线段DY上的点X在三角形ABC内部。(含在边界的情形)
|
s***5 发帖数: 203 | 49 有意思,这个题出的有点二义性,或者说不同的解题人有不同理解。我原来以为,两个
三角形都固定了。
那我倒要问问,ABC 坐标是{ (0,0), (1,0), (0,2) }, DEF坐标是 { (0,0), (1,0),
(0,-2)}
按照您的说法,ABC能覆盖DEF吗?
如果能,请给出平移和/或旋转,使得D,E,F全在ABC内部。
如果不能,请根据您自己列的充要条件解释。
【在 l***o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 充要条件是DEF经过适当平移和旋转后,D,E,F全在ABC内部或边界上。或者说可以找到 : 一个平移和旋转,使得D,E,F三点在ABC内部或边界上。 : : 形)
|
s*******a 发帖数: 4166 | 50 这个就有点钻牛角尖了,我已经说过了,这个是我在机场等飞机的时候想到的一个问题
,表达不精确也属难免。
你可以这么理解,给你一个三角形的盒子,再给你一个三角形的cookie,找到能把
cookie放进盒子里的充要条件,当然假设都是2D的。这问题也可以推广到三维(4面体
的盒子,4面体的粽子,呵呵)
,
【在 s***5 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 有意思,这个题出的有点二义性,或者说不同的解题人有不同理解。我原来以为,两个 : 三角形都固定了。 : 那我倒要问问,ABC 坐标是{ (0,0), (1,0), (0,2) }, DEF坐标是 { (0,0), (1,0), : (0,-2)} : 按照您的说法,ABC能覆盖DEF吗? : 如果能,请给出平移和/或旋转,使得D,E,F全在ABC内部。 : 如果不能,请根据您自己列的充要条件解释。
|
|
|
s***5 发帖数: 203 | 51 好了,出题人解释了,明白了。
ABC 坐标是{ (0,0), (1,0), (0,2) }, DEF坐标是 { (0,0), (1,0), (0,-2)}。
按照菠萝的充要条件,ABC不能覆盖DEF。
按照你的cookie模型,ABC就能覆盖DEF。
【在 s*******a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个就有点钻牛角尖了,我已经说过了,这个是我在机场等飞机的时候想到的一个问题 : ,表达不精确也属难免。 : 你可以这么理解,给你一个三角形的盒子,再给你一个三角形的cookie,找到能把 : cookie放进盒子里的充要条件,当然假设都是2D的。这问题也可以推广到三维(4面体 : 的盒子,4面体的粽子,呵呵) : : ,
|
s*******a 发帖数: 4166 | 52 thanks soze's proof. I think the proof I modified is good and clean. Please
let me know if there is anything wrong in the proof.
(x
后A
【在 s*******a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 刚才在等飞机,做了点brain teaser打发时间,后来自己想到这个问题: : 2个给定的三角形,如何判断一个能否被另一个三角形覆盖?不知道有没有比较初等的 : 方法,想了半天没想出来。
|
l***o 发帖数: 7937 | 53 You are not correct in saying 按照菠萝的充要条件,ABC不能覆盖DEF。I don't
have time to explain why because I am too busy right now. Maybe flip or
mirror or reflection should be added to the condition.
【在 s***5 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 好了,出题人解释了,明白了。 : ABC 坐标是{ (0,0), (1,0), (0,2) }, DEF坐标是 { (0,0), (1,0), (0,-2)}。 : 按照菠萝的充要条件,ABC不能覆盖DEF。 : 按照你的cookie模型,ABC就能覆盖DEF。
|
s**e 发帖数: 1834 | 54 包子已收到,谢谢。
Please
【在 s*******a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : thanks soze's proof. I think the proof I modified is good and clean. Please : let me know if there is anything wrong in the proof. : : (x : 后A
|
s***5 发帖数: 203 | 55 you got it! Need to add flip/reflection.
【在 l***o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : You are not correct in saying 按照菠萝的充要条件,ABC不能覆盖DEF。I don't : have time to explain why because I am too busy right now. Maybe flip or : mirror or reflection should be added to the condition.
|
l***o 发帖数: 7937 | 56 For clarity, yes. But remember reflection is a special case of rotation. It
is a special case of rotation of 180°about a line (which you choose) in xy
plane passing through the origin. This way the problem can be well defined
mathematically and the math formulation should not be that complicated.
【在 s***5 的大作中提到】![](/moin_static193/solenoid/img/up.png) : you got it! Need to add flip/reflection.
|
s**e 发帖数: 1834 | 57 这个直角三角形的假设和31楼
的想法有些类似,我在34楼
解释了一下为什么失去了一般性。
Please
【在 s*******a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : thanks soze's proof. I think the proof I modified is good and clean. Please : let me know if there is anything wrong in the proof. : : (x : 后A
|