bzoj1185【HNOI2007】最小矩形覆蓋
Description
凸包+旋轉卡殼
首先有一個結論：矩形一定有一條邊在凸包上，否則我們旋轉之後一定會得到一個更小的矩形，腦補一下。
然後枚舉凸包上的邊，用旋轉卡殼維護矩形的另外三條邊，同時更新答案即可。
#include
#include
#include
#include
#include
#include
#include
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define maxn 50005
#define eps 1e-8
#define inf 1e60
using namespace std;
int n,top;
double mn=inf;
struct data
{
double x,y;
friend bool operator ==(data a,data b){return fabs(a.x-b.x)(data a,data b){return !(a==b)&&!(a0;
}
inline void solve()
{
F(i,2,n) if (p[i]1&&(p[i]-s[top-1])*(s[top]-s[top-1])>-eps) top--;
s[++top]=p[i];
}
}
inline void getans()
{
int l=1,r=1,p=1;
double L,R,D,H;
s[0]=s[top];
F(i,0,top-1)
{
D=dis(s[i],s[i+1]);
while ((s[i+1]-s[i])*(s[p+1]-s[i])-(s[i+1]-s[i])*(s[p]-s[i])>-eps) p=(p+1)%top;
while ((s[i+1]-s[i])/(s[r+1]-s[i])-(s[i+1]-s[i])/(s[r]-s[i])>-eps) r=(r+1)%top;
if (i==0) l=r;
while ((s[i+1]-s[i])/(s[l+1]-s[i])-(s[i+1]-s[i])/(s[l]-s[i])
