Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

我的方法

Posted by huangchang9001 at 2011-07-11 02:07:14 on Problem 2628
这题是正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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator