旋转卡壳求最小矩形覆盖
cpp
double get_project(Point a, Point b, Point c){
return dot(b - a, c - a) / (b - a).length();
}
vector<Point> get_min_rectangle(vector<Point> hull,double &min_area){
// 旋转卡壳求最小矩形覆盖
// andrew判断需要改成<=
// ans[4]四个顶点逆序
if(is_line(hull)){
min_area=0;
return {hull[0],hull[0],hull.back(),hull.back()};
}
vector<Point> ans(4);
int n=hull.size();
hull.push_back(hull[0]);
for(int i=0,a=2,b=1,c=2;i<n;i++){
auto d=hull[i],e=hull[i+1];
while(cmp(area(d,e,hull[a]),area(d,e,hull[a+1]))<0)a=(a+1)%n;
while(cmp(get_project(d,e,hull[b]),get_project(d,e,hull[b+1]))<0)b=(b+1)%n;
if(!i)c=a;
while(cmp(get_project(d,e,hull[c]),get_project(d,e,hull[c+1]))>0)c=(c+1)%n;
auto x=hull[a],y=hull[b],z=hull[c];
auto h=area(d,e,x)/(e-d).length();
auto w=dot(y-z,e-d)/(e-d).length();
if(h*w<min_area){
min_area=h*w;
ans[0] = d + (e - d).norm() * get_project(d, e, y);
ans[3] = d + (e - d).norm() * get_project(d, e, z);
auto u = (rotate(e - d, -PI / 2)).norm();
ans[1] = ans[0] + u * h;
ans[2] = ans[3] + u * h;
}
}
for(int i=0;i<4;i++){
if(!sign(ans[i].x))ans[i].x=0;
if(!sign(ans[i].y))ans[i].y=0;
}
return ans;
}