Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
我的方法这题是正n边形桌子,每个顶点一条腿,选取一组顶点,要使cut后桌子稳定,那么桌子重心一定在这组定点组成的多边形内(且不在边上) 其实可以发现一条规律,正n边形可以看作一个环A,你选的一组顶点也是一个环B{a,b,d,e},这组定点中一个点a出发(顺时针),经过环A的点,最后到于与点a相邻的且是要走的最后一个e直接到a,在这个路程中,走了m个点即a,b,c,d,e, 我要说的是m与n,满足关系式m>(n-2)/2+2,则重心必在环B内。注意要保证m是最小值,如果从b出发按顺时针路径则是b,c,d,e,f,a.会错误。 a--b / \ f c \ / e--d 剩下的就是对腿进行排序,从大到小,先求最长的三条腿的顶点是否满足条件,不满足加如第四长腿的定点于环B中,一次循环。有相同长度的腿不会对结果造成影响,可以自己分析! 那个关系式,是根据偶数正多边形会有对角线在经过重心时想出来的! Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator