品牌形象网站源码/网络平台的推广方法

传送门:bzoj1185

题解

洛谷上非常卡精度。

先求出凸包。

显然最小矩形的某种方案是存在一条边与凸包上的某条边重合的(否则旋转一下即可)。

所以枚举边，旋转卡壳求出对踵点，还有对应的最左最右点。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long double db;
const db eps=1e-10;
const int N=5e4+10;int n,top,stk[N];db ans=1e233;inline int dcmp(db x) {if(fabs(x)<eps) return 0;return x<0?-1:1;}struct P{db x,y;P(db _x=0,db _y=0):x(_x),y(_y){};bool operator <(const P&ky)const{if(dcmp(y-ky.y)==0) return dcmp(x-ky.x)<1;return dcmp(y-ky.y)<1;}db operator ^(const P&ky){return x*ky.y-y*ky.x;}db operator *(const P&ky){return x*ky.x+y*ky.y;}P operator -(const P&ky){return P(x-ky.x,y-ky.y);}P operator *(const db&ky){return P(x*ky,y*ky);}P operator +(const P&ky){return P(x+ky.x,y+ky.y);}
}p[N],t[N],mn,q[5];inline db sqr(db x){return x*x;}
inline db dist(P a,P b){return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));}inline bool cmp(P a,P b)
{int res=dcmp((a-mn)^(b-mn));if(!res) return (dist(a,mn)<dist(b,mn));return res==1;
}inline bool onlf(P a,P b,P c){return dcmp((c-b)^(a-b))>-1;}inline void graham()
{int i,j;for(i=2;i<=n;++i) if(t[i]<t[1]) swap(t[i],t[1]);stk[++top]=1;mn=t[1];sort(t+2,t+n+1,cmp);for(i=2;i<=n;++i){for(;top>1 && onlf(t[stk[top]],t[stk[top-1]],t[i]);--top);stk[++top]=i;}
}inline void sol()
{int i,l=1,r=1,op=1;P dlt;for(i=1;i<=top;++i) p[i]=t[stk[i]];p[0]=p[top];db L,R,D,H;for(i=0;i<top;++i){D=dist(p[i],p[i+1]);dlt=p[i+1]-p[i];for(;dcmp((dlt^(p[op+1]-p[i]))-(dlt^(p[op]-p[i])))>-1;op=(op+1)%top);for(;dcmp((dlt*(p[r+1]-p[i]))-(dlt*(p[r]-p[i])))>-1;r=(r+1)%top);if(!i) l=r;for(;dcmp((dlt*(p[l+1]-p[i]))-(dlt*(p[l]-p[i])))<1;l=(l+1)%top);L=(dlt*(p[l]-p[i]))/D;R=(dlt*(p[r]-p[i]))/D;H=fabs(dlt^(p[op]-p[i]))/D;if((R-L)*H<ans){ans=(R-L)*H;q[0]=p[i]+(dlt*(R/D));q[1]=q[0]+((p[r]-q[0])*(H/dist(p[r],q[0])));q[2]=q[1]+((p[i]-q[0])*((R-L)/dist(p[i],q[0])));q[3]=q[0]+(q[2]-q[1]);}}
}inline double trs(db x){int res=dcmp(x);if(!res) return 0;return (double)x;}int main(){int i,j=0;double a,b;scanf("%d",&n);for(i=1;i<=n;++i) {scanf("%lf%lf",&a,&b);t[i]=P((db)a,(db)b);}graham();sol();for(i=1;i<4;++i) if(q[i]<q[j]) j=i;printf("%.5lf\n",trs(ans));for(i=0;i<4;++i)printf("%.5lf %.5lf\n",trs(q[(j+i)%4].x),trs(q[(j+i)%4].y));return 0;}

(算几写起来总是不太顺手。。。