1 条题解

  • 1
    @ 2022-9-5 15:22:59
    #include<algorithm>
    #include<cstring>
    #include<cstdio>
    #include<cmath>
    #define LD double
    #define LL long long
    #define Vector Point
    #define Re register int
    using namespace std;
    const int N=1e6+3;
    const LD eps=1e-8;
    inline int dcmp(LD a){return a<-eps?-1:(a>eps?1:0);}
    int n,t;LD ans=1e18;
    inline void in(Re &x){
        int f=0;x=0;char c=getchar();
        while(c<'0'||c>'9')f|=c=='-',c=getchar();
        while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
        x=f?-x:x;
    }
    struct Point{int x,y;Point(Re X=0,Re Y=0){x=X,y=Y;}}P[N],cp[N];
    inline LL Cro(Vector a,Vector b){return (LL)a.x*b.y-(LL)a.y*b.x;}
    inline Vector operator-(Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);}
    inline bool cmp(const Point &A,const Point &B){return A.x!=B.x?A.x<B.x:A.y>B.y;}
    inline LD getk(Point a,Point b){return (LD)(a.y-b.y)/(a.x-b.x);}
    inline LD calc(Point a,LD k){return dcmp(k)?a.x+a.y-a.x*k-a.y/k:1e18;}
    int main(){
    //    freopen("123.txt","r",stdin);
        in(n);
        for(Re i=1;i<=n;++i)in(P[i].x),in(P[i].y);
        sort(P+1,P+n+1,cmp);
        for(Re i=1;i<=n;++i){
            while(t>1&&Cro(cp[t]-cp[t-1],P[i]-cp[t-1])>=0)--t;
            cp[++t]=P[i];
        }
        for(Re i=1;i<=t;++i){
            LD k=-sqrt((LD)cp[i].y/cp[i].x);
            if((i==1||dcmp(k-getk(cp[i],cp[i-1]))<=0)&&(i==t||dcmp(k-getk(cp[i],cp[i+1])>=0)))ans=min(ans,calc(cp[i],k));
            if(i>1)ans=min(ans,calc(cp[i],getk(cp[i],cp[i-1])));
            if(i<t)ans=min(ans,calc(cp[i],getk(cp[i],cp[i+1])));
        }
        printf("%.4lf\n",ans);
    }
    
    • 1

    信息

    ID
    2227
    时间
    1000ms
    内存
    125MiB
    难度
    6
    标签
    递交数
    2
    已通过
    2
    上传者