自动搬运

查看原文

来自洛谷，原作者为

	辰星凌 时过而不知泪已落 —散华礼弥

搬运于2025-08-24 21:47:23，当前版本为作者最后更新于2020-04-22 21:18:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

【题解】妖怪 [SCOI2016] [P3291] [Bzoj4570]

$\mathcal{My}\ \mathcal{Blog}$

传送门：妖怪 $\text{[SCOI2016] P3291]}$ $\text{[Bzoj4570]}$

【题目描述】

给出 $n$ $(n\leqslant 10^6)$ 个点 $(x_i,y_i)$，设 $f_i(a,b)=x_i+y_i+\frac{bx_i}{a}+\frac{ay_i}{b}$，求出一组 $(a,b)$，使得 $\max\{f_{i\in[1,n]}(a,b)\}$ 最小，输出这个最小值。

【分析】

感觉网上很多题解都没讲清楚。

【Solution #1】

设 $k=\frac{b}{a}$，则上面的函数可以转换为 $f_i(k)=x_i+y_i+kx_i+\frac{y_i}{k}$ 。

求最大的最小很明显要二分，每次检查是否存在一个正实数 $k$ 满足所有点的 $f(k)$ 都小于等于 $mid$ 。即判断这个不等式组是否有解：

$\begin{cases}f_1(k)\leqslant mid\\f_2(k)\leqslant mid\\...\\f_n(k)\leqslant mid \end{cases}$

易知 $f_i$ 是一个双勾函数， 我们可以通过解关于 $k$ 的一元二次方程 $f_i(k)=mid$ 得出 $k$ 的一（两）个解 $r_1,r_2$ $(r_1\leqslant r_2)$，则当 $k\in[r_1,r_2]$ 时一定满足 $f_i(k)\leqslant mid$ 。对所有点求出 $k$ 的合法区间，最后判断是否存在交集即可。

时间复杂度：$O(n\log \inf)$，可能会 $TLE$，但卡一卡貌似能水过。

代码就不放了（懒）。

【Solution #2】

此为正解。

设 $k=-\frac{b}{a}$，则 $f_i(k)=x_i+y_i-kx_i-\frac{y_i}{k}$（依然是双勾函数）。

假设有一条斜率为 $k$ 且经过了点 $(x_i,y_i)$ 的直线，则该直线点斜式可表示为 $y=kx+(y_i-kx_i)$，其横纵截距分别为 $\frac{kx_i-y_i}{k}$ 和 $y_i-kx_i$ 。

把这玩意儿加起来试试？

$(\frac{kx_i-y_i}{k})+(y_i-kx_i)=x_i+y_i-kx _i-\frac{y_i}{k}$

发现其表示式和 $f_i(k)$ 一模一样！。

也就是说 $f_i(k)$ 的实质是斜率为 $k$ 且过点 $(x_i,y_i)$ 的直线横纵截距之和。

假设当前 $k$ 已经确定，则计算 $\max\{f_{i\in[1,n]}(k)\}$ 的过程就是个线性规划，易知该直线与上凸包的切点处 $f(k)$ 值最大。

反过来想，对于凸包上的每一个点 $i$，考虑在什么情况下 $f_i(k)$ 大于等于其他所以点的 $f(k)$，然后在合法情况中找到最小的 $f_i$ 来更新答案。设点 $i$ 在凸包上左右相邻两点与 $i$ 所形成的直线斜率分别为 $k_1,k_2$ $(k_1 > k_2)$，则仅当 $k$ 在 $(-\infty,k_2]\cup [k_1,\infty)$ 中取值时合法（只有此时才能满足直线与凸包切点恰好为 $i$）

已知当 $-k=\frac{y_i}{x_i}$ 时 $f_i$ 可取得最小值（均值不等式），如果 $k=-\frac{y_i}{x_i}$ 在上述合法值域内，那么 $f_i(-\frac{y_i}{x_i})$ 就可以作为一个答案的候选项。

如果 $k=-\frac{y_i}{x_i}$ 不在上述合法区域内，那么就要想办法找到其他 $k$ 使得 $f_i(k)$ 尽量小，由于双勾函数的性质， $k$ 越接近 $-\frac{y_i}{x_i}$ 函数值就越小，所以直接取 $k=kr$ 和 $k=kl$ 的情况进行决策即可。

除了求上凸包要排序，决策都是线性的，时间复杂度：$O(n\log n)$ 。

（毒瘤 $OI$ 的算几依旧是这么毒瘤，不过这次代码长度倒是挺良心的）

【Code】

#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);
}