题意：n维空间中，最小化某点a到固定有界超平面P \(\sum{p_i} = 1, p_i \geq 0 \) 的距离。输入的坐标为分母固定的分数，输出答案的最简分数。
如果这题没有有界限制，直接套n维空间的距离公式就行了。然后考虑有界限制的情况。
几何乱搞法
因为我太菜，没有看出这是一个裸的对偶凸优化问题(机器学习忘完了)，只好暴力从几何上推。
首先要判断什么情况下可以使用距离公式，显然是点的投影在超平面内部的情况。
投影点p可以直接算：\[\vec p +t(1,1,1,\cdots)=\vec a \]两边各项求和， \[1 + nt =\sum{a_i},\\ t=\frac{\sum{a_i}-1}{n}\]
但是投影不在可行域内怎么办？以三维为例，可能最优的p在边界线上，也可能在边界点上。可以发现，在边界线上的情况，可以用二维的距离公式+剩下一维的平方，前面那部分相当于在n-1维的子空间中做同样的问题。于是可以把坐标值排序，依次弹出投影在负数的维度坐标。被弹出的部分直接求平方和，剩下的用距离公式就可以了。
#include <bits/stdc++.h>using namespace std;
typedef long long ll;
ll a[10010];
struct frac{
ll a, b;void r(){ll g=__gcd(abs(a),b); a/=g; b/=g;}
void prt(){if (a==0 || b==1) printf("%lld\n",a); else printf("%lld/%lld\n",a,b);}
frac operator-(const frac &v)const{return (frac){a*v.b-b*v.a,b*v.b};}
};
int main(){
ll n,m;while (~scanf("%lld%lld",&n,&m)){
ll sa=0, sa2=0;
for (int i=0;i<n;i++) scanf("%lld",a+i),sa+=a[i],sa2+=a[i]*a[i];
sort(a,a+n);
int i;
for (i=0;i<n;i++){
frac d=(frac){a[i],m}-(frac){sa-m,(n-i)*m};
if (d.a>=0) break;
sa-=a[i];
}sa2=0;
for (int j=0;j<i;j++){
sa2+=a[j]*a[j];
}sa-=m;
frac ans=(frac){sa*sa+(n-i)*sa2,m*m*(n-i)};
ans.r();
ans.prt();
}return 0;
}
不过这个弹出最小负值我没证明是不是一定对，而且平面法向量不是全1的时候应该不能这么搞。
upd1: 好像是对的，不妨设投影的某一个坐标不满足约束条件。那么从删去这一维的n-1维上看，其他坐标的n维超平面投影条件实际上比n-1上的松，所以不会误删除维度。
拉格朗日乘子法
然后推一下标算解法。这是一个已经把目标函数和限制条件都摆在题目上的最优化问题，而且是单纯的二次规划+凸优化：
\[\mathop{\arg\min}\limits_{\vec p} dis(\vec a,\vec p)\\ {\rm s.t.} \ \sum{p_i}=1\\p_i\geq 0 \]
写出原始问题：
\[\mathop{\min}\limits_{p\geq 0} \mathop{\max}\limits_\lambda L(p,\lambda)\\ L(p,\lambda) = dis(\vec a, \vec p) + \lambda (\sum{p_i}-1)\]
然后显然这里决策边界为凸而且目标函数为凸，满足KKT条件。交换min、max得到对偶问题并展开：
\[\mathop{\max}\limits_\lambda \mathop{\min}\limits_{p\geq 0} L(p,\lambda)\\ L(p,\lambda) = \sum{(a_i-p_i)^2} + \lambda (\sum{p_i}-1)\\=\sum{(a_i^2 -2a_i p_i + p_i ^2 + \lambda p_i)}-2\lambda \]
对p配方以分离出p：
\[=\sum{\Big(\big(p_i+(\frac{\lambda}{2}-a_i)\big)^2+a_i^2-(\frac{\lambda}{2}-a_i)^2\Big)}-2\lambda\\
=\sum{(p_i+(\frac{\lambda}{2}-a_i))^2}+\sum{(-\frac{\lambda^2}{4}+\lambda a_i)}-2\lambda \]
调整p对第部分的每一项求min，则\[ \mathop{\min}\limits_{p\geq 0}\ (p_i+(\frac{\lambda}{2}-a_i))^2 = (\mathop{\min}\{0, \frac{\lambda}{2}-a_i\})^2 \]
终于得到了一个只关于λ的函数，它是分段函数而且每一段都是二次函数。对每个分段区间算一次最大值即可。