题解 P3291 【[SCOI2016]妖怪】

辰星凌 · 2020-04-22 21:18:51 · 题解

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

\mathcal{My}\ \mathcal{Blog}

传送门：[妖怪 \text{[SCOI2016] P3291]}](https://www.luogu.com.cn/problem/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 。即判断这个不等式组是否有解：

易知 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 。

把这玩意儿加起来试试？

发现其表示式和 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);
}