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 lx_c at 2007-09-23 20:16:42 on Problem 3301
标准正放正方形的比较好做只要找出 minx,miny,maxx,maxy即可
但是最小正方形不一定是标准正放,
由于题目中的点只有30个
因此有两种穷举的思路(不是精确解)
一:穷举每个小角度变化值的正方形的四条边,看是否所有点在四条边内部,本方法要求计算几何水平很高
二:穷举每个点对角度坐标表换的值,然后求标准正放的最小正方形即可,相对第一种方法此方法简单明了,且编码容易

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