思路:

首先有一个显然的性质:就是最小矩形必定有一条边与凸包的边重合.

然后我们自然就是对于每一条边考虑一下:首先找到距离这条边最远的点.然后从这个点到这条边做一条垂线段,用这条垂线段上下平移来得到两个边界.

于是我用旋转卡壳找最远的点,然后对于两边分别三分.

效率好像还不低.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
 
typedef double f2;
 
static const f2 eps=1e-7;
inline int dcmp(const f2&x){return fabs(x)<eps?0:(x<0?-1:1);}
 
#define N 50010
struct Point{
    f2 x,y;
    Point(){}
    Point(f2 _x,f2 _y):x(_x),y(_y){}
     
    inline void read(){scanf("%lf%lf",&x,&y);}
    inline void print(){printf("%.5lf %.5lf\n",x,y);}
     
    bool operator<(const Point&B)const{return fabs(x-B.x)==0?y<B.y:x<B.x;}
     
    Point operator+(const Point&B)const{return Point(x+B.x,y+B.y);}
    Point operator-(const Point&B)const{return Point(B.x-x,B.y-y);}
    Point operator*(const f2&p)const{return Point(x*p,y*p);}
};
 
Point getvec(const Point&v){return Point(-v.y,v.x);}
Point getmid(const Point&a,const Point&b){return Point((a.x+b.x)/2,(a.y+b.y)/2);}
 
f2 getdis(const Point&a,const Point&b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
f2 cross(const Point&a,const Point&b){return a.x*b.y-a.y*b.x;}
f2 area(const Point&a,const Point&b,const Point&c){return fabs(cross(a-b,a-c))*.5;}
 
struct Line{
    Point p,v;
    Line(Point p1,Point p2,bool d){p=p1,v=d?p1-p2:p2;}
};
 
Point getlineintersection(const Line&l1,const Line&l2){
    return l1.p+l1.v*(cross(l1.p-l2.p,l2.v)/cross(l1.v,l2.v));
}
 
Point P[N],stk[N<<1];int top;
 
Point move(Point p,Point v,f2 l){
    return p+v*(l/sqrt(v.x*v.x+v.y*v.y));
}
 
f2 res=1e10;
Point re[N];
 
int main(){
    //freopen("tt.in","r",stdin);
    int n;scanf("%d",&n);
    register int i,j;
     
    for(i=1;i<=n;++i)P[i].read();
     
    sort(P+1,P+n+1);
    int ins;for(ins=n;ins!=1&&dcmp(P[ins].x-P[ins-1].x)==0;--ins);
    for(i=ins;i<=(n+ins)/2;++i)swap(P[i],P[n+ins-i]);
     
    for(i=1;i<=n;++i){
        if(!top)stk[++top]=P[i];
        else{while(top>=2&&dcmp(cross(stk[top-1]-stk[top],stk[top]-P[i]))<=0)--top;stk[++top]=P[i];}
    }
    int instk=top;
    for(i=ins-1;i>=1;--i){
        if(top==instk)stk[++top]=P[i];
        else{while(top>=instk+1&&dcmp(cross(stk[top-1]-stk[top],stk[top]-P[i]))<=0)--top;stk[++top]=P[i];}
    }--top;
     
    for(i=top+1;i<=2*top;++i)stk[i]=stk[i-top];
     
    int r=2,L,R,ll,rr;
    f2 h1,h2;
    for(i=1;i<=top;++i){
        while(area(stk[i],stk[i+1],stk[r])<=area(stk[i],stk[i+1],stk[r+1]))++r;
         
        Line l1=Line(stk[i],stk[i+1],1);
        Line l2=Line(stk[r],getvec(l1.v),0);
        Point pr=getlineintersection(l1,l2);
         
        h1=h2=0;
        for(L=i+1,R=r;;){
            if(R-L+1<=5){for(j=L;j<=R;++j)h1=max(h1,area(stk[r],pr,stk[j])*2/getdis(stk[r],pr));break;}
             
            ll=L+(R-L+1)/3,rr=R-(R-L+1)/3;
            if(area(stk[r],pr,stk[ll])<=area(stk[r],pr,stk[rr]))L=ll;else R=rr;
        }
        for(L=r,R=i+top;;){
            if(R-L+1<=5){for(j=L;j<=R;++j)h2=max(h2,area(stk[r],pr,stk[j])*2/getdis(stk[r],pr));break;}
             
            ll=L+(R-L+1)/3,rr=R-(R-L+1)/3;
            if(area(stk[r],pr,stk[ll])<=area(stk[r],pr,stk[rr]))L=ll;else R=rr;
        }
         
        if(getdis(stk[r],pr)*(h1+h2)<res){
            res=getdis(stk[r],pr)*(h1+h2);
            re[0]=move(pr,stk[i]-stk[i+1],h1);
            re[1]=move(stk[r],stk[i]-stk[i+1],h1);
            re[2]=move(stk[r],stk[i+1]-stk[i],h2);
            re[3]=move(pr,stk[i+1]-stk[i],h2);
        }
    }
     
    printf("%.5lf\n",res);
    int bins;Point Minre;
    for(Minre=re[0],bins=0,i=1;i<4;++i)if(dcmp(re[i].y-Minre.y)<0||(dcmp(re[i].y-Minre.y)==0&&dcmp(re[i].x-Minre.x)<0))Minre=re[i],bins=i;
     
    for(i=0;i<4;++i)re[(i+bins)%4].print();
     
    return 0;
}

思路:

我们发现最终的答案就是缩小一圈后的矩形的顶点们形成的凸包的周长再加上一个半径为\(r\)的圆的周长.

因为多边形外角和为\(360\)度.这个不用多说.

此外还有一点点问题就是旋转后的坐标变换.

如果是\((x,y)\)以原点为旋转中心逆时针旋转\(\alpha\)弧度,那么新的坐标为\((xcos\alpha-ysin\alpha,xsin\alpha+ycos\alpha)\).

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
 
typedef double f2;
 
#define N 200010
 
static const f2 eps=1e-8;
inline int dcmp(const f2&x){return (fabs(x)<eps)?0:(x<0?-1:1);}
 
struct Point{
    f2 x,y;
    Point(){}
    Point(f2 _x,f2 _y):x(_x),y(_y){}
     
    Point operator+(const Point&B)const{return Point(x+B.x,y+B.y);}
    Point operator-(const Point&B)const{return Point(B.x-x,B.y-y);}
    Point operator*(const f2&p)const{return Point(p*x,p*y);}
    Point operator/(const f2&p)const{return Point(x/p,y/p);}
     
    bool operator<(const Point&B)const{return dcmp(x-B.x)==0?(dcmp(y-B.y)<0):(dcmp(x-B.x)<0);}
}P[N<<2],PP[N<<2],stk[N<<2];
 
f2 getdis(const Point&a,const Point&b){
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
Point move(const Point&p,const f2&Ang,const f2&x,const f2&y){
    return Point(p.x*cos(Ang)-p.y*sin(Ang)+x,p.x*sin(Ang)+p.y*cos(Ang)+y);
}
 
int main(){
    int n;scanf("%d",&n);
     
    f2 a,b,r,x,y,Ang;scanf("%lf%lf%lf",&a,&b,&r);a-=2*r,b-=2*r;
     
    register int i,j;
    int cnt=0;
    for(i=1;i<=n;++i){
        scanf("%lf%lf%lf",&x,&y,&Ang);
         
        P[++cnt]=move(Point(b/2,a/2),Ang,x,y);
        P[++cnt]=move(Point(-b/2,a/2),Ang,x,y);
        P[++cnt]=move(Point(b/2,-a/2),Ang,x,y);
        P[++cnt]=move(Point(-b/2,-a/2),Ang,x,y);
    }
     
    int top=0;
    sort(P+1,P+cnt+1);
    int revins;for(revins=cnt;revins!=1&&P[revins].x==P[revins-1].x;--revins);
    for(i=revins;i<=(n+revins)/2;++i)swap(P[i],P[n+revins-i]);
     
    for(i=1;i<=cnt;++i){
        if(!top)stk[++top]=P[i];
        else{while(top>1&&(P[i].y-stk[top].y)*(stk[top].x-stk[top-1].x)<=(stk[top].y-stk[top-1].y)*(P[i].x-stk[top].x))--top;stk[++top]=P[i];}
    }
    int nowtop=top;
    for(i=revins-1;i>=1;--i){
        if(top==nowtop)stk[++top]=P[i];
        else{while(top>=nowtop+1&&(P[i].y-stk[top].y)*(stk[top].x-stk[top-1].x)<=(stk[top].y-stk[top-1].y)*(P[i].x-stk[top].x))--top;stk[++top]=P[i];}
    }--top;
     
    f2 re=0;
    for(i=1;i<top;++i)re+=getdis(stk[i],stk[i+1]);re+=getdis(stk[top],stk[1]);
     
    printf("%.2lf",re+2*acos(-1.0)*r);
     
    return 0;
}

思路:
首先\(O(n^3)\)的思路非常朴素,只需要考虑每条向量的贡献即可.向量的出现概率即为这两个点出现且向量右侧的点均不出现.于是我们需要暴力\(O(n)\)check右侧的点是否均不出现.

我们考虑以一个点为起点的所有向量的答案.

那么对于每一个向量右侧的点必定都是一段区间,且满足单调性.

我们枚举起点,然后把剩下的点按照关于起点的极角序排序,然后依次扫描即可.

当然有几个坑点:

概率有一些为0的不能直接乘除,而需要记录零的个数.

还有就是坑爹的三点共线问题.

我们考虑当角度相同时,按照距离从大到小排序.

然后扫描的时候进行一些特判.这里没太弄明白就先挖坑了.

(好像一开始先把点随机扰动一下应该也可以吧)

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
 
typedef double f2;
 
#define N 1010
struct Point{
    f2 x,y,p;
    Point(){}
    Point(f2 _x,f2 _y):x(_x),y(_y){}
    Point operator+(const Point&B)const{return Point(x+B.x,y+B.y);}
    Point operator-(const Point&B)const{return Point(B.x-x,B.y-y);}
    Point operator*(const f2&p)const{return Point(p*x,p*y);}
}P[N];
inline f2 sqr(const f2&x){return x*x;}
inline f2 cross(const Point&a,const Point&b){return a.x*b.y-a.y*b.x;}
inline f2 dot(const Point&a,const Point&b){return a.x*b.x+a.y*b.y;}
inline f2 length(const Point&a){return sqrt(sqr(a.x)+sqr(a.y));}
 
static const f2 eps=1e-8;
inline int dcmp(const f2&x){return fabs(x)<eps?0:(x<0?-1:1);}
 
struct Seg{
    Point v;
    f2 Ang,area,p,len;
    inline bool operator<(const Seg&B)const{
        return dcmp(Ang-B.Ang)==0?len>B.len:Ang<B.Ang;
    }
}S[N];
 
int main(){
    int n;scanf("%d",&n);register int i,j,k;
    for(i=0;i<n;++i)scanf("%lf%lf%lf",&P[i].x,&P[i].y,&P[i].p),P[i].p/=1000.0;
    f2 ans=0;
    for(i=0;i<n;++i){
        int id=0;
        for(j=0;j<n;++j)if(i^j){
            S[id].v=P[i]-P[j];
            S[id].Ang=atan2(S[id].v.y,S[id].v.x);
            S[id].area=cross(P[i],P[j]);
            S[id].p=P[j].p;
            S[id].len=length(S[id].v);
            id++;
        }
        sort(S,S+id);
        long double nowp=P[i].p;
        int zero=0;
        for(j=0;j<id;++j)if(dcmp(S[j].p-1)==0)++zero;else nowp*=(1-S[j].p);
         
        k=0;
        for(j=0;j<id;++j){
            while(dcmp(cross(S[j].v,S[k].v))>0||(dcmp(cross(S[j].v,S[k].v))==0&&dcmp(dot(S[k].v,S[j].v-S[k].v))<=0)){
                if(dcmp(1-S[k].p))nowp/=1-S[k].p;else --zero;
                k=(k+1)%id;
                if(k==j)break;
            }
            if(!zero)ans+=S[j].area*nowp*S[j].p;
            if(dcmp(1-S[j].p)!=0)nowp*=(1-S[j].p);else ++zero;
        }
    }
     
    printf("%.6lf",ans*.5);
    return 0;
}