洛谷P3291 [SCOI2016]妖怪题解

题目链接：P3291 [SCOI2016]妖怪

题意：

邱老师是妖怪爱好者，他有 \(n\) 只妖怪，每只妖怪有攻击力 \(\mathtt{atk}\) 和防御力 \(\mathtt{dnf}\) 两种属性。邱老师立志成为妖怪大师，于是他从真新镇出发，踏上未知的旅途，见识不同的风景。

环境对妖怪的战斗力有很大影响，在某种环境中，妖怪可以降低自己 \(ka\) 点攻击力，提升 \(kb\) 点防御力或者，提升自己 \(ka\) 点攻击力，降低 \(kb\) 点防御力。 \(a,b \in \mathbb{R}_{+},~k \in \mathbb{R}\) ，但是 \(\mathtt{atk}\) 和 \(\mathtt{dnf}\) 必须始终非负。

妖怪在环境 \((a,b)\) 中的战斗力为妖怪在该种环境中能达到的最大攻击力和最大防御力之和 \[ \mathtt{strength}(a,b)=\max\{\mathtt{atk}(a,b)\}+\max\{\mathtt{dnf}(a,b)\} \] 环境由 \(a,b\) 两个参数定义，\(a,b\) 的含义见前文描述。

比如当前环境 \(a=3,~b=2\) ，那么攻击力为 \(6\) ，防御力为 \(2\) 的妖怪，能达到的最大攻击力为 \(9\) ，最大防御力为 \(6\) 。所以该妖怪在 \(a=3,~b=2\) 的环境下战斗力为 \(15\) 。

因此，在不同的环境，战斗力最强的妖怪可能发生变化。

作为一名优秀的妖怪训练师，邱老师想发掘每一只妖怪的最大潜力，他想知道在最为不利的情况下，他的 \(n\) 只妖怪能够达到的最强战斗力值，即存在一组正实数 \((a,b)\) 使得 \(n\) 只妖怪在该环境下最强战斗力最低。

输入格式：

第一行一个 \(n\) ，表示有 \(n\) 只妖怪。

接下来n行，每行两个整数 \(\mathtt{atk}\) 和 \(\mathtt{dnf}\) ，表示妖怪的攻击力和防御力。

输出格式：

输出在最不利情况下最强妖怪的战斗力值，保留4位小数。

数据范围：

\(1\le n\le 10^6, 0＜\mathtt{atk},\mathtt{dnf}\le 10^8\)

关键词：黄金分、二维凸包、对勾函数性质。

感觉这题需要一定的观察能力。~~反正我没有QAQ~~

注：如果你也和我一样啥也没发现然后死推式子的，可以翻到这篇文章末尾

然后你会发现死推式子也是可以发现这个性质的。当然，死推式子甚至也要观察。

注意到这个系数 \(k\) 是没有整数限制的，

因此其实这个题和 \(a,b\) 本身没关系，而和 \(a,b\) 的比例有关。

为什么呢？因为你「用 \(1\) 份攻击买 \(2\) 份防御」和「用 \(2\) 份攻击买 \(4\) 份防御」是一个意思

对它来说就是变了变系数 \(k\) 。（感谢 Roundgod 老师的耐心指导）

于是我们设 \(k=\frac{b}{a}\) ，然后我们把攻击力为 \(x\) ，防御力为 \(y\) 的妖怪看作平面上的点

然后我们可以发现它的 \(x,y\) 取值范围与斜率为 \(-k\) 的直线有关

而它的战斗力就是该直线在横纵轴上的截距之和。如图。

问题就转化为找到一个 \(k\) ，使得斜率为 \(k\) 的直线过每个已知点得到的「横纵截距之和」的最大值最小。

不难发现，对答案有影响的点在原点集的上凸壳上。于是我们先跑一个二维凸包求下上凸壳。

根据对勾函数的性质（~~那个和的式子都会推吧~~），又因为若干个单峰函数的最大值还是单峰函数

注：单峰函数是在所考虑的区间中只有一个严格局部极大值(峰值)的实值函数。

考虑三分斜率 \(k\) 。

事实上用「黄金分割比」去分（即黄金分），常数更小。

然后就尝试了一下... 还是三分好记...

时间复杂度 \(\mathcal{O}(n \log n + C \,|\log \epsilon|)\) ，其中 \(C\) 为上凸壳点数，\(\epsilon\) 为精度 eps。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define INF 0x3f3f3f3f3f3f3f3f
#define N ((int)(1e6+15))
const double PHI=0.6180339887498948482;
const double eps=4e-12;

int n,top,stk[N];
struct vct{double x,y;}p[N],c[N];
#define pf(x) ((x)*(x))
vct operator+(vct a,vct b){return {a.x+b.x,a.y+b.y};}
vct operator-(vct a,vct b){return {a.x-b.x,a.y-b.y};}
vct operator*(vct a,double b){return {a.x*b,a.y*b};}
vct operator/(vct a,double b){return {a.x/b,a.y/b};}
double cross(vct a,vct b){return a.x*b.y-a.y*b.x;}
double dot(vct a,vct b){return a.x*b.x+a.y*b.y;}
double len(vct a){return sqrt(pf(a.x)+pf(a.y));}
int cmp(vct a,vct b){return a.x==b.x ? a.y<b.y : a.x<b.x;}
void up(double &x, double y) { x < y ? x = y : 0;}
double f(double x)
{
    double res=-1e233;
    for(int i=1; i<=n; i++)
        up(res, c[i].x * (x + 1.0) + c[i].y * (1.0/x + 1.0));
    return res;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cout << fixed << setprecision(4);
    cin >> n;
    for(int i=1; i<=n; i++) cin >> p[i].x >> p[i].y;
    sort(p+1,p+1+n,cmp); stk[++top]=1;
    for(int i=2; i<=n; i++)
    {
        // 上凸壳
        while(top>1 && cross(p[stk[top]] - p[stk[top-1]], p[i] - p[stk[top]]) > eps)
            stk[top--]=0;
        stk[++top]=i;
    } n=top;
    for(int i=1; i<=n; i++) c[i]=p[stk[i]];
    double l,r,d,fl,fr,ml,mr;
    l = 0.0001, r = 10000.000, d = (r-l) * PHI;
    fl = f(ml = r-d), fr = f(mr = l+d);
    while(d > 4e-12)
    {
        d *= PHI;
        if(fl <= fr)
        {
            r=mr; mr=ml; fr=fl; fl = f(ml = r-d);
        }else
        {
            l=ml; ml=mr; fl=fr; fr = f(mr = l+d);
        }
    }
    cout << fl << '\n';
    return 0;
}

~~死推式子都会吧~~

题目转化为给定 \(n\) 个点 \((x_i,y_i)\) ，找到一组 \((a,b)\) ，最小化下面的式子 \[ \max_{1 \le i \le n}\left\{f_i = x_i + y_i + \frac{bx_i}{a} + \frac{ay_i}{b}\right\} \] 设 \(k=-\frac{b}{a}\) ，得 \[ \begin{aligned} f_i &= x_i + y_i - kx_i - \frac{y_i}{k} \\ &= \left(\frac{kx_i - y_i}{k}\right) + \left(y_i - kx_i\right) \end{aligned} \] 这不就是过点 \((x_i,y_i)\) 斜率为 \(k\) 的直线在 \(y\) 轴上的横纵截距之和吗？（点斜式方程如下） \[ y = kx + (y_i - kx_i) \] 然后问题就转化为找到一个 \(k\) ，使得斜率为 \(k\) 的直线过每个已知点得到的 \(f_i\) （横纵截距之和）最大值最小。