1 .最小面積外接矩形
類似的擎值，要求得外接矩形，則要求出矩形的寬和高鲫忍，而高的求法已經(jīng)知道了膏燕，是利用叉積求面積的方法可以求出高，而寬則可以用點(diǎn)積來(lái)求悟民。
先來(lái)看看點(diǎn)積的幾何意義：
假設(shè)Ｓ為旋轉(zhuǎn)卡殼中的枚舉邊坝辫，Ｆ為待定的右邊界，那么要使得右邊界最右射亏，即右邊的寬度（Ｆ*cos(Θ) )越長(zhǎng)近忙，則他們的點(diǎn)積要越大
類似的，左邊界的點(diǎn)積要越小
矩形面積
題意：
求.最小面積外接矩形
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int MAXN=4010;
const double EPS=1e-10;
const double INF=1e20;
struct Point
{
double x,y;
Point(double x=0,double y=0):x(x),y(y){}
};
Point in[MAXN],out[MAXN];
typedef Point Vector;
bool operator <(const Point &a,const Point &b)
{
return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
Vector operator -(Vector A,Vector B)
{
return Vector(A.x-B.x,A.y-B.y);
}
double cross(Vector A,Vector B)
{
return A.x*B.y-A.y*B.x;
}
double dot(Vector A,Vector B)
{
return A.x*B.x+A.y*B.y;
}
int convexHull(Point *p,int n,Point *ch)
{
sort(p,p+n);
int m=0;
for(int i=0;i<n;i++)
{
while(m>1&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
ch[m++]=p[i];
}
int k=m;
for(int i=n-2;i>=0;i--)
{
while(m>k&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
ch[m++]=p[i];
}
if(n>1) m--;
return m;
}
double length(Vector A)
{
return sqrt(A.x*A.x+A.y*A.y);
}
double rotateCalipers(Point *p,int n)
{
int up=1,rig=1,lef;
p[n]=p[0];
double ans=INF;
for(int i=0;i<n;i++)
{
while(cross(p[i+1]-p[i],p[up]-p[i])<cross(p[i+1]-p[i],p[up+1]-p[i])) up=(up+1)%n;//上邊界
while(dot(p[i+1]-p[i],p[rig]-p[i])<dot(p[i+1]-p[i],p[rig+1]-p[i])) rig=(rig+1)%n;//右邊界
if(i==0) lef=rig;
while(dot(p[i+1]-p[i],p[lef]-p[i])>=dot(p[i+1]-p[i],p[lef+1]-p[i])) lef=(lef+1)%n;//左邊界智润，這里必須有等于號(hào)
double len=length(p[i+1]-p[i]);
double area=(cross(p[i+1]-p[i],p[up]-p[i])/len)*(dot(p[i+1]-p[i],p[rig]-p[i])/len-dot(p[i+1]-p[i],p[lef]-p[i])/len);
//cross(p[i+1]-p[i],p[up]-p[i])/len為矩形的高及舍，(dot(p[i+1]-p[i],p[rig]-p[i])/len-dot(p[i+1]-p[i],p[lef]-p[i])/len)為矩形的寬
//左邊界的點(diǎn)積dot(p[i+1]-p[i],p[lef]-p[i])有可能小于0
if(ans>area) ans=area;
}
return ans;
}
int main()
{
int t,n;
scanf("%d",&t);
for(int cas=1;cas<=t;cas++)
{
scanf("%d",&n);
n*=4;
for(int i=0;i<n;i++)
{
scanf("%lf%lf",&in[i].x,&in[i].y);
}
int res=convexHull(in,n,out);
double area=rotateCalipers(out,res);
printf("Case #%d:\n%.f\n",cas,area);
}
}
類似題目：
Smallest Bounding Rectangle
題解：注意要特判，只有一個(gè)點(diǎn)的時(shí)候直接輸出0,如果求旋轉(zhuǎn)卡殼會(huì)造成死循環(huán)做鹰，因?yàn)榍笞筮吔缬械扔谔?hào)的緣故
2.求凸包間的最小距離
原理類似击纬，就是不斷求邊與邊的最短距離就可以了
就是初始化有點(diǎn)不一樣：
左邊的凸包尋找最低點(diǎn)鼎姐，右邊的凸包尋找最高點(diǎn)
凸包最短距離專用圖
Bridge Across Islands
題意：
求凸包間的最短距離
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const double EPS=1e-10;
const double INF=1e20;
const int MAXN=10010;
struct Point
{
double x,y;
Point(double x=0,double y=0):x(x),y(y){}
};
Point p1[MAXN],p2[MAXN];
typedef Point Vector;
int dcmp(double val)
{
if(abs(val)<EPS) return 0;
return val>0?1:-1;
}
Vector operator-(Vector A,Vector B)
{
return Vector(A.x-B.x,A.y-B.y);
}
bool operator ==(const Point &a,const Point &b)
{
return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0;
}
double cross(Vector A,Vector B)
{
return A.x*B.y-A.y*B.x;
}
double dot(Vector A,Vector B)
{
return A.x*B.x+A.y*B.y;
}
double length(Vector A)
{
return sqrt(A.x*A.x+A.y*A.y);
}
double disToSegment(Point p,Point a,Point b)
{
if (a==b) return length(p-a);
if(dcmp(dot(b-a,p-a))<0) return length(p-a);
else if(dcmp(dot(a-b,p-b))<0) return length(p-b);
else return abs(cross(p-b,a-b))/length(a-b);
}
double disLineToLine(Point a,Point b,Point c,Point d)//兩線段間的最短距離
{
//對(duì)應(yīng)四種情況
return min(min(min(disToSegment(a,c,d),disToSegment(b,c,d)),disToSegment(c,a,b)),disToSegment(d,a,b));
}
double rotateCalipers(Point *p,int n,Point *s,int m)
{
int minp=0,maxs=0;
for(int i=1;i<n;i++)
{
if(p[i].y<p[minp].y) minp=i;
}
for(int i=1;i<m;i++)
{
if(s[i].y>p[maxs].y) maxs=i;
}
p[n]=p[0];
s[m]=s[0];
double dis=INF,tmp;
for(int i=0;i<n;i++)
{
//如果maxs+1到邊(minp,minp+1)的距離比maxs到邊(minp,minp+1)的距離近,那么maxs向前走,距離用的是叉積求三角形面積來(lái)判斷
while(cross(p[minp]-p[minp+1],s[maxs+1]-p[minp+1])-cross(p[minp]-p[minp+1],s[maxs]-p[minp+1])<-EPS) maxs=(maxs+1)%m;
dis=min(dis,disLineToLine(p[minp],p[minp+1],s[maxs],s[maxs+1]));//兩線間的最短距離
minp=(minp+1)%n;
}
return dis;
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF,n+m)
{
for(int i=0;i<n;i++)
{
scanf("%lf%lf",&p1[i].x,&p1[i].y);
}
for(int i=0;i<m;i++)
{
scanf("%lf%lf",&p2[i].x,&p2[i].y);
}
double dis=rotateCalipers(p1,n,p2,m);
printf("%.5f\n",dis);
}
}
3.給定多個(gè)點(diǎn)钾麸，求任意三點(diǎn)的最大的三角形面積
首先，我們知道最大的三角形的點(diǎn)一定是在多點(diǎn)形成的凸包上炕桨，但是最大三角形的邊卻不一定是凸包的邊饭尝。
設(shè)三個(gè)起點(diǎn)i=0，j=1献宫，k=2钥平，每次都先移動(dòng)k，直到面積最大姊途，然后移動(dòng)j直到面積最大涉瘾，然后移動(dòng)i直到面積最大，因?yàn)檫@個(gè)過程中面積是不斷增加的捷兰，所以移動(dòng)完在取最大值吧立叛，不用每移動(dòng)一次都求，如果三個(gè)點(diǎn)都不變的話贡茅，強(qiáng)制移動(dòng)k秘蛇。用vis數(shù)組來(lái)表示訪問狀態(tài)其做，當(dāng)vis[2]時(shí)表示已經(jīng)訪問一圈，然后結(jié)束循環(huán)赁还。
C - Triangle
題意：
求解平面中的點(diǎn)中任意取三個(gè)能夠形成最大的三角形面積妖泄。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const double EPS=1e-10;
const double INF=1e20;
const int MAXN=50010;
struct Point
{
double x,y;
Point(double x=0,double y=0):x(x),y(y){}
};
Point in[MAXN],out[MAXN];
typedef Point Vector;
bool operator<(const Point &a,const Point &b)
{
return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
Vector operator -(Vector A,Vector B)
{
return Vector(A.x-B.x,A.y-B.y);
}
double cross(Vector A,Vector B)
{
return A.x*B.y-A.y*B.x;
}
double dot(Vector A,Vector B)
{
return A.x*B.x+A.y*B.y;
}
int convexHull(Point *p,int n,Point *ch)
{
sort(p,p+n);
int m=0;
for(int i=0;i<n;i++)
{
while(m>1&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
ch[m++]=p[i];
}
int k=m;
for(int i=n-2;i>=0;i--)
{
while(m>k&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
ch[m++]=p[i];
}
if(n>1) m--;
return m;
}
int vis[MAXN];
double rotateCalipers(Point *p,int n)
{
if(n<3) return 0;
p[n]=p[0];
int i=0,j=1,k=2,a,b,c;
double area=-INF,tmp;
memset(vis,0,sizeof(vis));
while(!vis[2])
{
a=i;b=j;c=k;
while(cross(p[j]-p[i],p[k]-p[i])<cross(p[j]-p[i],p[k+1]-p[i])) k=(k+1)%n,vis[k]=1;
while(cross(p[j]-p[i],p[k]-p[i])<cross(p[j+1]-p[i],p[k]-p[i])) j=(j+1)%n;
while(cross(p[j]-p[i],p[k]-p[i])<cross(p[j]-p[i+1],p[k]-p[i+1])) i=(i+1)%n;
area=max(area,cross(p[j]-p[i],p[k]-p[i]));
if(a==i&&b==j&&c==k) k=(k+1)%n,vis[k]=1;
}
return area/2;
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF,n+1)
{
for(int i=0;i<n;i++)
{
scanf("%lf%lf",&in[i].x,&in[i].y);
}
int res=convexHull(in,n,out);
double area=rotateCalipers(out,res);
printf("%.2f\n",area);
}
}
還有一種暴力枚舉的方法，時(shí)間復(fù)雜度為O(N^2)就是任意枚舉兩條邊艘策，借助旋轉(zhuǎn)卡殼尋找最大面積三角形
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const double EPS=1e-10;
const double INF=1e20;
const int MAXN=50010;
struct Point
{
double x,y;
Point(double x=0,double y=0):x(x),y(y){}
};
Point in[MAXN],out[MAXN];
typedef Point Vector;
bool operator<(const Point &a,const Point &b)
{
return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
Vector operator -(Vector A,Vector B)
{
return Vector(A.x-B.x,A.y-B.y);
}
double cross(Vector A,Vector B)
{
return A.x*B.y-A.y*B.x;
}
double dot(Vector A,Vector B)
{
return A.x*B.x+A.y*B.y;
}
int convexHull(Point *p,int n,Point *ch)
{
sort(p,p+n);
int m=0;
for(int i=0;i<n;i++)
{
while(m>1&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
ch[m++]=p[i];
}
int k=m;
for(int i=n-2;i>=0;i--)
{
while(m>k&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
ch[m++]=p[i];
}
if(n>1) m--;
return m;
}
double rotateCalipers(Point *p,int n)
{
p[n]=p[0];
int up;
double area=-INF,tmp;
for(int i=0;i<n;i++)//枚舉邊i,j
{
up=i+1;
for(int j=i+1;j<n;j++)
{
while(cross(p[j]-p[i],p[up+1]-p[i])>cross(p[j]-p[i],p[up]-p[i])) up=(up+1)%n;
tmp=cross(p[j]-p[i],p[up]-p[i]);
if(tmp>area) area=tmp;
}
}
return area/2;
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF,n+1)
{
for(int i=0;i<n;i++)
{
scanf("%lf%lf",&in[i].x,&in[i].y);
}
int res=convexHull(in,n,out);
double area=rotateCalipers(out,res);
printf("%.2f\n",area);
}
}
