傳送門(mén)

題意：求最小矩陣覆蓋

有這樣一個(gè)結(jié)論：矩陣一定有一條邊在凸包上（不會(huì)證）

那可以枚舉每條邊
同時(shí)旋轉(zhuǎn)卡殼
只是這時(shí)不只維護(hù)一個(gè)對(duì)踵點(diǎn)對(duì)，同時(shí)在左右側(cè)再維護(hù)一個(gè)最遠(yuǎn)點(diǎn)
可以發(fā)現(xiàn)左右最遠(yuǎn)點(diǎn)一定是和當(dāng)前邊點(diǎn)積最小/最大的
不斷統(tǒng)計(jì)答案就是了

注意$printf$遇到$0.000$會(huì)輸出$?0.0000$，要特判一下

#include<bits/stdc++.h> using namespace std; inline int read(){char ch=getchar();int res=0,f=1;while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}while(isdigit(ch))res=res*10+(ch^48),ch=getchar();return res*f; } const int N=50005; const double pi=acos(-1); const double eps=1e-8; struct point{double x,y;point(double a=0,double b=0){x=a,y=b;}friend inline point operator +(const point &a,const point &b){return point(a.x+b.x,a.y+b.y);}friend inline point operator -(const point &a,const point &b){return point(a.x-b.x,a.y-b.y);}friend inline double operator *(const point &a,const point &b){return (a.x*b.y-a.y*b.x);}friend inline point operator *(const point &a,const double &b){return point(a.x*b,a.y*b);}friend inline double operator /(const point &a,const point &b){return a.x*b.x+a.y*b.y;}inline double calc(){return sqrt(x*x+y*y);} }p[N],q[N],t[5]; inline bool comp(const point &a,const point &b){double res=(a-p[1])*(b-p[1]);return (res==0)?((a-p[1]).calc()<(b-p[1]).calc()):(res>0); } int n,top; double ans=1e9; inline void graham(){int idx=1;for(int i=2;i<=n;i++){if(p[idx].y>p[i].y||(p[idx].y==p[i].y&&p[i].x<p[idx].x))idx=i;}if(idx!=1)swap(p[idx],p[1]);sort(p+2,p+n+1,comp);q[++top]=p[1];for(int i=2;i<=n;++i){while(top>=3&&((p[i]-q[top-1])*(q[top]-q[top-1])>=0))top--;q[++top]=p[i];}q[0]=q[top]; } inline void solve(){int l=1,r=1,h=1;for(int i=0;i<top;i++){double dis=(q[i]-q[i+1]).calc();while((q[i+1]-q[i])*(q[h+1]-q[i])-(q[i+1]-q[i])*(q[h]-q[i])>-eps)h=(h+1)%top;while((q[i+1]-q[i])/(q[r+1]-q[i])-(q[i+1]-q[i])/(q[r]-q[i])>-eps)r=(r+1)%top;if(i==0)l=r;while((q[i+1]-q[i])/(q[l+1]-q[i])-(q[i+1]-q[i])/(q[l]-q[i])<eps)l=(l+1)%top;double lg=(q[i+1]-q[i])/(q[l]-q[i])/dis,rg=(q[i+1]-q[i])/(q[r]-q[i])/dis;double ht=(q[i+1]-q[i])*(q[h]-q[i])/dis;if(ht<0)ht=-ht;if((rg-lg)*ht<ans){ans=(rg-lg)*ht;t[0]=q[i]+(q[i+1]-q[i])*(rg/dis);t[1]=t[0]+(q[r]-t[0])*(ht/(q[r]-t[0]).calc());t[2]=t[1]+(q[i]-t[0])*((rg-lg)/(q[i]-t[0]).calc());t[3]=t[2]+(t[0]-t[1]);}} } int main(){n=read();for(int i=1;i<=n;i++){scanf("%lf%lf",&p[i].x,&p[i].y);}graham();solve();if(ans<eps)cout<<"0.00000\n";else printf("%.5lf\n",ans);int d=0;for(int i=1;i<=3;i++){if(t[i].y<t[d].y||(t[i].y==t[d].y&&t[i].x<t[d].x))d=i;}for(int i=0;i<=3;i++){if(t[(i+d)%4].x<eps)cout<<"0.00000 ";else printf("%.5lf ",t[(i+d)%4].x);if(t[(i+d)%4].y<eps)cout<<"0.00000\n";else printf("%.5lf\n",t[(i+d)%4].y);} }

轉(zhuǎn)載于:https://www.cnblogs.com/stargazer-cyk/p/11145656.html

總結(jié)

以上是生活随笔為你收集整理的【BZOJ1185】【HNOI2007】最小矩形覆盖（凸包+旋转卡壳）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。