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

Re:我的思路,不同意见的可以交流哦

Posted by bsshanghai at 2011-06-05 16:10:22 on Problem 2079
In Reply To:我的思路,不同意见的可以交流哦 Posted by:skogt at 2010-07-27 21:27:21
这个复杂度是O(n^2long(n))吧.

> 
> 先建立一个凸包,在这些点中选取最大的三角形面积,很容易想到组成三角形的点在凸包边界上;
> 然后用旋转卡壳;这个东西我也要好好的学习一下
> 枚举三角形的第一个顶点i,
> 然后初始第二个顶点j=i+1,第三个顶点k=j+1,
> 循环k+1直到Area(i,j,k)>Area(i,j,k+1)
> 更新面积的最大值,下面就开始旋转卡壳了(旋转j,k两个点)
> (1)如果Area(i,j,k)
> (2)更新面积,j=j+1,如果j=i,跳出循环
> 这样旋转一圈后,求得的面积就是以i为顶点的最大三角形的面积了。
> 时间复杂度是O(n^2)

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