计算几何 vfleaking提供Spj

#include<cstdio>#include<cmath>#include<algorithm>using namespace std;const int N=1e5+5;const double eps=1e-8;double ans=1e60;struct Vector{    double x,y;    Vector(double x=0,double y=0):x(x),y(y){}}p[N],q[N],t[5];int n,top;Vector operator + (Vector A,Vector B){return Vector(A.x+B.x,A.y+B.y);}Vector operator - (Vector A,Vector B){return Vector(A.x-B.x,A.y-B.y);}Vector operator * (Vector A,double p){return Vector(A.x*p,A.y*p);}Vector operator / (Vector A,double p){return Vector(A.x/p,A.y/p);}double operator * (Vector A,Vector B){return A.x*B.y-A.y*B.x;;}double operator / (Vector A,Vector B){return A.x*B.x+A.y*B.y;;}bool operator<(Vector a,Vector b){    return fabs(a.y-b.y)<eps?a.x<b.x:a.y<b.y;}bool operator==(Vector a,Vector b){    return fabs(a.x-b.x)<eps&&fabs(a.y-b.y)<eps;}double Dot(Vector A,Vector B){return A.x*B.x+A.y*B.y;}double Length(Vector A){return sqrt(Dot(A,A));}double Angle(Vector A,Vector B){return acos(Dot(A,B)/(Length(A)*Length(B)));}double Cross(Vector A,Vector B){return A.x*B.y-A.y*B.x;}double Area2(Vector A,Vector B,Vector C){return Cross(B-A,C-A);}bool cmp(Vector a,Vector b){    double t=(a-p[1])*(b-p[1]);    if(fabs(t)<eps) return Length(p[1]-a)-Length(p[1]-b)<0;    else return t>0;}void graham(){//凸包     for(int i=2;i<=n;i++) if(p[i]<p[1]) swap(p[i],p[1]);    sort(p+2,p+n+1,cmp);    q[++top]=p[1];    for(int i=2;i<=n;i++){        while(top>1&&(q[top]-q[top-1])*(p[i]-q[top])<eps) top--;        q[++top]=p[i];    }    q[0]=q[top];}void RC(){//旋转卡壳     int l=1,r=1,p=1;    double L,R,D,H;    for(int i=0;i<top;i++){        D=Length(q[i]-q[i+1]);        while((q[i+1]-q[i])*(q[p+1]-q[i])-(q[i+1]-q[i])*(q[p]-q[i])>-eps) p=(p+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;            L=(q[i+1]-q[i])/(q[l]-q[i])/D,R=(q[i+1]-q[i])/(q[r]-q[i])/D;        H=(q[i+1]-q[i])*(q[p]-q[i])/D;        if(H<0) H=-H;        double tmp=(R-L)*H;        if(tmp<ans){            ans=tmp;            t[0]=q[i]+(q[i+1]-q[i])*(R/D);            t[1]=t[0]+(q[r]-t[0])*(H/Length(t[0]-q[r]));            t[2]=t[1]-(t[0]-q[i])*((R-L)/Length(q[i]-t[0]));            t[3]=t[2]-(t[1]-t[0]);        }    }}int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);    graham();    RC();    printf("%.5lf\n",ans);    int fir=0;    for(int i=1;i<4;i++) if(t[i]<t[fir]) fir=i;    for(int i=0;i<4;i++){//某些OJ评测卡精度.. 比如，洛谷        if(fabs(t[(i+fir)%4].x)<1e-6) printf("0.00000 ");else printf("%.5lf ",t[(i+fir)%4].x);        if(fabs(t[(i+fir)%4].y)<1e-6) printf("0.00000\n");else printf("%.5lf\n",t[(i+fir)%4].y);    }    return 0;}/*Sample Input61.0 3.000001 4.000002.00000 13 0.000003.00000 66.0 3.0Sample Output18.000003.00000 0.000006.00000 3.000003.00000 6.000000.00000 3.00000*/