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 SevenR at 2019-07-01 09:40:22 on Problem 3301 and last updated at 2019-07-01 09:41:27
In Reply To:如何证明三分法成立？此题为何是单峰函数？ Posted by:bingshen at 2011-07-22 09:13:05 
三分是错的
求出点集的凸包，用旋转卡壳求出O(n)个f(theta) = 平行线间距离可能改变单调性的点，则任意两个点之间f单调，g(theta) = max(f(theta),f(theta + 90°))^2是拟凸的，这样再三分(设k为三分次数)，复杂度是T*n^2*k的。
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