Prutekoi's blog

首先，这个问题可以模拟退火做。（如吊打XXX）
当函数被证明只有单峰时，可以爬山。

偏导

对于一个多元函数（以二元函数为例） $f(x,y)$，可以看作是自变量是多维空间上的点。偏导的定义即为对于一个点，向其中某一维度走一个极小值，函数值变化值与走的距离的比值。计算时把无关的自变量看作常数即可。
如 $f(x,y)=x^2+2xy+y$，则 $\frac{df}{dx}=2x+2y,\frac{df}{dy}=2x+1$。
那么多元函数函数 $f(x,y)$ 的极值点需要满足的条件就是对于所有自变量的偏导都为 $0$。
这样可以列出一个方程组，若它只有一组解，则这个极值点就是最值点，我们就不用退火了。

BZOJ2508

求一个点使得它到平面上所有直线距离平方和最小。
你需要实现以下3种操作：

1. 平面上加入一条直线；
2. 删除一条已加入的直线；
3. 求一个点到平面上所有直线距离平方和最小，你需要输出这个最小值。
   首先，点到直线距离公式为 $\frac{Ax+By+C}{\sqrt{A^2+B^2}}$，平方一下就可以得到一个二元二次函数，有六项。所有直线的对应系数相加，最后需要做的就是最优化这个二元二次函数。那直接求偏导就OK了。
   需要注意的是，当当前所有直线都平行时，极值点也是一条直线，所以偏导为0列出的两个方程是线性相关的。所以发现一个有效的方程解出一个特解就OK了。

然后有一个特别坑的地方就是数据有锅，答案的输出中有-0.00。。。。
然后这题还有一个不用偏导，只用到初中知识的推式子方法。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+50;
const double eps=1e-9;
int n,m;double a[N],b[N],c[N],d[N],A,B,C,D,E,F;
void add(int id,int k){
    double x=a[id],y=b[id],z=c[id],w=d[id];
    A+=k*x*x/w;B+=k*y*y/w;C+=2*k*x*y/w;
    D+=2*k*x*z/w;E+=2*k*y*z/w;F+=k*z*z/w;
}
double calc(){
    double x,y;
    if(abs(4*A*B-C*C)>eps)y=(C*D-2*A*E)/(4*A*B-C*C),x=(C*E-2*B*D)/(4*A*B-C*C);
    else{
        if(abs(A)<eps&&abs(B)<eps)x=0,y=0;
        else if(abs(A)>eps)x=-D/A/2,y=0;
        else y=-E/B/2,x=0;
    }
    return A*x*x+B*y*y+C*x*y+D*x+E*y+F;
}
int main(){
    scanf("%d",&n);
    for(int i=1,op,x;i<=n;i++){
        scanf("%d",&op);
        if(!op){
            double x1,y1,x2,y2;++m;
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            a[m]=y2-y1,b[m]=x1-x2,c[m]=y1*x2-x1*y2;
            d[m]=a[m]*a[m]+b[m]*b[m];add(m,1);
        }
        else if(op==1)scanf("%d",&x),add(x,-1);
        else printf("%.2f\n",calc()+eps);
    }
    return 0;
}

有些问题是需要让多元函数的自变量之间满足一些等量关系的。我们把自变量看作一个向量 x，则这个问题可描述成给出一些多元函数 $\varphi(x)$，都要满足 $\varphi(x)=0$，再求 $f(x)$ 的极值。我们可以对于每个函数 $\varphi(x)$ 引入一个变量 $\lambda$，也看作向量，构造拉格朗日函数 $L(x,\lambda)=f(x)+\sum\lambda_i\varphi_i(x)$
求这个新的多元函数的极值点对应的函数值即为满足条件的原函数的极值。

（我们发现WQS二分其实就是这个东西吧）这题，然后注意如果需要变量是整数，那么导数可以换成离散差分。

因为极值点需满足各个方向偏导为 $0$，那么对 $\lambda_i$ 的偏导为 $0$ 就是满足了 $\varphi_i(x)=0$。
然后裸题就是骑行川藏，需要注意的是发现大部分方程中的变量都是只有 $\lambda$ 和 $v_i$，那么可以考虑把 $\lambda$ 看作参数用 $\lambda$ 表示每个 $v_i$。这是基本的数学套路吧QAQ，都忘光了不会了

（约束条件也可以是不等式的，这个先咕着吧）