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 xuhaoran510 at 2011-04-09 19:40:52 on Problem 3178 and last updated at 2011-04-09 19:42:37
1.判定哪些树桩之间是不能连绳子的
  我的方法:枚举树桩i,j和麦田怪圈k
          首先,如果i或j在怪圈k的范围内,绳子肯定是不能连的。
          然后算出直线(i,j)到怪圈k圆心的距离(这个很简单,叉积乱搞就可以了……),如果大于半径R,就一定不会与k相交了
          然后用点积算出k与线段(i,j)的相对位置,如果dot(i,j,k)与dot(j,i,k)异号,那么一定不会与k相交,否则一定会
          
2.DP求出最优解
  我的方法:因为是个凸包,如果用dp[i,j]表示第i个到第j个树桩这一段的最优解的话,有
          dp[i,j]=max{dp[i,k]+dp[k,j] i<k<j}+ok[i,j]
          ok[i,j]为1如果i到j可以连绳子,否则为0
          边界情况自己考虑……
然后dp[1,n]就是答案了
注意:在读入树桩的位置后需要极角排序……

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