最小矩形覆盖

本文主要是介绍最小矩形覆盖，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

#include<bits\stdc++.h>
using namespace std;
#define int long long
void in(int &x){
    int    y=1;char c=getchar();x=0;
    while(c<'0'||c>'9'){if(c=='-')y=-1;c=getchar();}
    while(c<='9'&&c>='0'){ x=(x<<1)+(x<<3)+c-'0';c=getchar();}
    x*=y;
}
const int _ = 1e6+10;
const double eps = 1e-9;
const double pi = cos(-1);
struct PT{
    double x,y;
    PT(double x=0,double y=0):x(x),y(y){}
    void input(){scanf("%lf%lf",&x,&y);}
    // 关键字排序
    bool operator<(const PT&p)const{
        if(fabs(x-p.x))return x<p.x;
            return y<p.y;
    }
    void output(){printf("%.10f %.10f\n",x,y);}
}p[_],q[_];
vector<PT>ret;
int n;

// 三点求叉积
double vect(PT p,PT p1,PT p2){
    return (p1.x-p.x)*(p2.y-p.y)-(p1.y-p.y)*(p2.y-p.y);
}
int  convex_hull(PT* p,int n,PT *q){
    int i,k,m;
    sort(p,p+n);
    m = 0;
    for(i=0;i<n;q[m++]=p[i++])while(m>1&&vect(q[m-2],q[m-1],p[i])<eps)m--;
    k=m;
    for(i=n-2;i>=0;q[m++]=p[i--])while(m>k&&vect(q[m-2],q[m-1],p[i])<eps)m--;
    return --m;
}
// ?
PT get(PT p,double x){
    return PT(p.x*cos(x)-p.y*sin(x),p.x*sin(x)+p.y*cos(x));
}
// ?
bool is_ext(int id,PT pp){
    if(
            vect(p[id],PT(p[id].x+pp.x,p[id].y+pp.y)
                 ,p[id+1])<-eps
                 )return 0;
    if(
            vect(p[id],PT(p[id].x+pp.x,p[id].y+pp.y),
                 p[(id-1+n)%n])<-eps
                 )return 0;
    return 1;
}
PT inter(PT p1,PT p2,PT p3,PT p4){
    p2.x+=p1.x;
    p2.y+=p1.y;
    p4.x+=p3.x;
    p4.y+=p3.y;
    double s=vect(p1,p2,p3),s1=vect(p1,p2,p4);
    double t=s/(s-s1);
    return PT(p3.x+(p4.x-p3.x)*t,p3.y+(p4.y-p3.y)*t);
}
double ans;
void solve(){
    int f[4];
    f[1]=f[2]=f[3]=0;
    for(int i=0;i<n;i++){
        f[0]=i;

        PT v[4];
        // 0-1的边
        v[0]=PT(p[i+1].x-p[i].x,p[i+1].y-p[i].y);
        //
        for(int j=1;j<4;j++)
            // 每个额外的点
            for(v[j]=get(v[0],pi/2*j);// v[j] 为 v[0] 选择 90°*j
            !is_ext(f[j],v[j]);
            f[j]=(f[j]+1)%n);
        vector<PT>tmp;

        for(int j=0;j<4;j++)tmp.push_back(inter(p[f[j]],v[j],p[f[(j+1)%4]],v[(j+1)%4]));
        double tmps=0;

        for(int j=0;j<4;j++)tmps+=vect(tmp[0],tmp[j],tmp[(j+1)%4]);
        tmps=fabs(tmps);
        if(ans>tmps)ans=tmps,ret=tmp;
    }
}
signed main(){
    while(~scanf("%d",&n)){
        if(!n)return 0;
        for(int i=0;i<n;i++)p[i].input();
        n=convex_hull(p,n,q);
        if(n<3)ans=0;else{
                for(int i=0;i<n;i++)p[i]=q[i];
                p[n]=p[0];
                ans=1e100;
                solve();
        }
        printf("%.4f\n",ans/2.0);
        //for(int i=0;i<4;i++)ret[i].output();
    }

    return 0;
}

这篇关于最小矩形覆盖的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！