題目：10173 - Smallest Bounding Rectangle

?

求凸包的最小外接矩形的面積。

思路：

旋轉卡殼
給定點集S,求S的最小覆蓋矩形
最小覆蓋矩形的四條邊上，其中一條邊有至少兩個點，其他邊上至少有一個點。
然后沿著凸包的邊旋轉，維護矩形另外三條邊上的點。

#include<stdio.h> #include<cmath> #include<algorithm> #define eps 1e-8 #define N 50010 using namespace std;struct Point {double x,y;Point(){}Point(double x0,double y0):x(x0),y(y0){} };Point p[N]; int con[N]; int cn; int n;struct Line {Point a,b;Line(){}Line(Point a0,Point b0):a(a0),b(b0){} };double Xmult(Point o,Point a,Point b) {return (a.x-o.x)*(b.y-o.y)-(b.x-o.x)*(a.y-o.y); } double Dmult(Point o,Point a,Point b) {return (a.x-o.x)*(b.x-o.x)+(a.y-o.y)*(b.y-o.y); }int Sig(double a) {return a<-eps?-1:a>eps; }double Dis(Point a,Point b) {return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); }int cmp(Point a,Point b) {double d=Xmult(p[0],a,b);if(d>0)return 1;if(d==0 && Dis(p[0],a)<Dis(p[0],b))return 1;return 0; }double min(double a,double b) {return a<b?a:b; }void Graham() {int i,ind=0;for(i=1;i<n;i++)if(p[ind].y>p[i].y || (p[ind].y==p[i].y) && p[ind].x>p[i].x)ind=i;swap(p[ind],p[0]);sort(p+1,p+n,cmp);con[0]=0;con[1]=1;cn=1;for(i=2;i<n;i++){while(cn>0 && Sig(Xmult(p[con[cn-1]],p[con[cn]],p[i]))<=0)cn--;con[++cn]=i;}int tmp=cn;for(i=n-2;i>=0;i--){while(cn>tmp && Sig(Xmult(p[con[cn-1]],p[con[cn]],p[i]))<=0)cn--;con[++cn]=i;} }double Solve() {int t,r,l;double ans=999999999;t=r=1;if(cn<3)return 0;for(int i=0;i<cn;i++){while(Sig( Xmult(p[con[i]],p[con[i+1]],p[con[t+1]])-Xmult(p[con[i]],p[con[i+1]],p[con[t]]) )>0)t=(t+1)%cn;while(Sig( Dmult(p[con[i]],p[con[i+1]],p[con[r+1]])-Dmult(p[con[i]],p[con[i+1]],p[con[r]]) )>0)r=(r+1)%cn;if(!i) l=r;while(Sig( Dmult(p[con[i]],p[con[i+1]],p[con[l+1]])-Dmult(p[con[i]],p[con[i+1]],p[con[l]]) )<=0)l=(l+1)%cn;double d=Dis(p[con[i]],p[con[i+1]]);double tmp=Xmult(p[con[i]],p[con[i+1]],p[con[t]])*( Dmult(p[con[i]],p[con[i+1]],p[con[r]])-Dmult(p[con[i]],p[con[i+1]],p[con[l]]) )/d/d;ans=min(ans,tmp);}return ans; }int main() {int i;while(scanf("%d",&n) && n){for(i=0;i<n;i++)scanf("%lf%lf",&p[i].x,&p[i].y);Graham();printf("%.4f\n",Solve());}return 0; }

?

總結

以上是生活随笔為你收集整理的UVA10173(求凸包的面积最小外接矩形)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。