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

传送门：妖怪 ( ext{[SCOI2016] P3291]}) ( ext{[Bzoj4570]})

【题目描述】

给出 (n) ((nleqslant 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_{iin[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) 。即判断这个不等式组是否有解：

(egin{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_1leqslant r_2))，则当 (kin[r_1,r_2]) 时一定满足 (f_i(k)leqslant mid) 。对所有点求出 (k) 的合法区间，最后判断是否存在交集即可。

时间复杂度：(O(nlog 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_{iin[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(nlog 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
",ans);
}