看板ACMCLUB
标 题world final problem G
发信站批踢踢兔 (Thu Apr 7 20:57:17 2005)
转信站ptt!Group.NCTU!grouppost!Group.NCTU!ptt2
它的充分必要条件似乎不是写的很严谨
congruent这个字在几何学上应该是可以旋转的
,但它这题的充分必要条件是不可旋转才会成立的吧?
另外我想到的解法是
如果它是解的话,必存在一种切法,使得分成两段後其中一段的起点是顶点X
另一段的端点也是顶点X (并非任意顶点都可以是X,所以每个顶点都要试)
根据长度必须一致,可以算出中点M(不一定是顶点)
中点M是第一段的端点,第二段的起点
接下来用greedy做最长比对
逐次移去共同最大boundary
超过3次的,根据它的充分必要条件,为无解,反之有解
--
※ 发信站: 批踢踢兔(ptt2.cc)
◆ From: 140.112.250.178