「BZOJ1185」[HNOI2007] 最小矩形覆盖

2014年12月24日8,2467

Description

题解

首先有一个结论,矩形的一条边一定在凸包上!!!
枚举凸包上的边
用旋转卡壳在凸包上找矩形另外三点。。。
注意精度问题

 

 

avatar
2 Comment threads
5 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
2 Comment authors
BPM136hzwer Recent comment authors
  Subscribe  
提醒
罗崚骁

敢问有一条边必在凸包上这个结论如何证明……

张凯羿

高亮没了

张凯羿

哦……是我的网速太渣了 = = 、