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 cuiaoxiang at 2009-09-23 22:43:49 on Problem 3135
In Reply To:Re:不理解。。。。。。 Posted by:ccnuzhang at 2009-09-23 22:00:32
把6条线段平均分成2部分
有C(6,3)种取法,对这2部分全排列,其中可以不妨设线段1在第一部分的第一个位置。这样有C(5,2)中取法,两部分枚举量分别是2!和3!。
对于每条线段把它分解成x^2+y^2最多有36种方向,其中9种在第一象限,其它的都是通过这9种基本的旋转得到。可以不妨设线段1的方向在第一象限。

然后对于前一部分3条保持右手旋转,后一部分3条保持左手旋转。同时旋转过程中没有自相交。因为只有3条线段,所以如果自相交只可能是第一条和第三条相交,加一个判断即可。由于要保持左右手旋转所以在每部分的第一条定了方向以后,后面线段的都只有36/2=18种选择。所以2部分枚举量分别是9*18*18和36*18*18。

从(0,0)出发分别对2部分左右手旋转,看他们最后能不能“对接”。如果能对接的话,除了起点和终点外其他的点都是凸的(想像成一个苹果,可能两头凹)。最后的6变形不一定是凸的,但是这个不要紧,最后这种非凸的6边形会被更优解替代掉(更优解其实可以把每个凹的地方进行“平行四边形替换”)。

这样第一部分可能有2!*9*18*18种终点位置,用map或者hashmap记录这个终点位置对应的面积的最大值。第二部分有3!*36*18*18种。实际操作的时候我假定第二部分的第一条线段方向也必须在第一象限,而让最后“对接”判断的时候多4被的工作量,这个是根据算法的瓶颈调整的。这样总枚举量是(2!+3!)*9*18*18*C(5,2)=2.3*10^5,
枚举最内层的是map和hashmap的操作,大约算一下知道map比hashmap慢10-20倍。
最后对接很简单,把2个hashmap扫一遍,这个不是瓶颈,所以可以尽量把前面枚举的常数放到这里来。

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