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 Essence_me at 2005-10-01 22:09:50 on Problem 1385
首先给你一系列有序的点,先判断顺时还是逆, (假设是顺时针)
然后连续的三个点,通过计算它的有向面积来判断这个角是否是凹的,如果是跳过,选下面连续的三个,
                如果不是,那么就计算这三个点组成三角形的重心,然后去掉三个点中间的那个点(在点集中)
这样重复上述过程,直到点集中只剩下三个点(当然计算最后一个重心就可以了)
这样我们就得到了一个由重心组成的集合,按任何顺序,两两求平均数,就可以得到最后的重心了,
这是我自己想的,,很可能比正规的算法麻烦很多,希望得到大家的指教

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