X轴上有N个点，每个点除了包括一个位置数据X[i]，还包括一个权值W[i]。该点到其他点的带权距离 = 实际距离 * 权值。求X轴上一点使它到这N个点的带权距离之和最小，输出这个最小的带权距离之和。
Input
第1行：点的数量N。(2 <= N <= 10000) 第2 - N + 1行：每行2个数，中间用空格分隔，分别是点的位置及权值。（-10^5 <= X[i] <= 10^5，1 <= W[i] <= 10^5)
Output
输出最小的带权距离之和。
Input示例
5 -1 1 -3 1 0 1 7 1 9 1
Output示例
20
三分~
神奇的我上来就写了个贪心，然后就WA了……
改成三分能A，三分的时候要注意所选位置不一定是给出的点的位置，必须用具体位置三分~
（所以为什么分类是中位数啊QAQ）
#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
#define ll long longconst ll inf=1e6;ll n,ans,l,r;struct node{ll a,v;
}a[10001];ll read()
{ll x=0,f=1;char ch=getchar();while(ch<'0' || ch>'9') {if(ch=='-') f=-1;ch=getchar();}while(ch>='0' && ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;
}ll cal(int u)
{ll ans=0;for(int i=1;i<=n;i++) ans+=abs(u-a[i].a)*a[i].v;return ans;
}int main()
{n=read();l=inf;r=-inf;for(int i=1;i<=n;i++) a[i].a=read(),a[i].v=read(),l=min(l,a[i].a),r=max(r,a[i].a);ll mid1,mid2,ans1,ans2;while(l+2<r){mid1=(l*2+r)/3;mid2=(l+r*2)/3;ans1=cal(mid1);ans2=cal(mid2);ans=min(ans1,ans2);if(ans1==ans2) l=mid1,r=mid2;else if(ans1<ans2) r=mid2;else l=mid1;}mid1=(l*2+r)/3;mid2=(l+r*2)/3;printf("%lld\n",min(min(cal(l),cal(r)),min(cal(mid1),cal(mid2))));return 0;
}