Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

包含已知点的面积最小的正方形框

Posted by lx_c at 2007-09-23 20:16:42 on Problem 3301

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

Followed by:

Re:包含已知点的面积最小的正方形框 (207) wanglishan0120 2010-09-12 14:00:17

Post your reply here:

Home Page Go Back To top