本文主要是介绍最小矩形覆盖,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
#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;
}
这篇关于最小矩形覆盖的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!