HDU 4355 Party All the Time（三分）
转载请注明出处，谢谢http://blog.csdn.net/acm_cxlove/article/details/7854526 by---cxlove
题目：坐标轴上有一些点，每个点有权值，找出一个位置，所有点到这个点的距离的三次方乘以权值的和最小。
http://acm.hdu.edu.cn/showproblem.php?pid=4355
根据题意如果中心为X0,Y0，那么结果为sigma(|Xi-X0|^3*W)。
这是一个凸函数，因为它的二次导大于0，适用于三分
练习赛的时候只听过三分，就瞎着YY了，不过最后还是爆ULL了，跪，没想到最后是用double直接处理
#include<iostream>#include<cstdio>#include<ctime>#include<cstring>#include<cmath>#include<algorithm>#include<cstdlib>#include<vector>#define C 240#define TIME 10#define eps 1e-7#define inf 1<<25#define LL unsigned long longusing namespace std;struct Node{ double x; double w;}a[50005];int n;double cal(double pos){ double sum=0; for(int i=0;i<n;i++) sum+=fabs(a[i].x-pos)*fabs(a[i].x-pos)*fabs(a[i].x-pos)*a[i].w; return sum;}int main(){ int t,cas=0; scanf("%d",&t); while(t--){ scanf("%d",&n); double low=1000000,high=-1000000; for(int i=0;i<n;i++){ scanf("%lf%lf",&a[i].x,&a[i].w); low=min(low,a[i].x); high=max(high,a[i].x); } printf("Case #%d: ",++cas); double midd,mid=(low+high)/2; while(fabs(high-low)>=eps){ mid=(low+high)/2; midd=(mid+high)/2; if(cal(mid)+eps<cal(midd)) high=midd; else low=mid; } double dist=cal(low); printf("%.0f\n",dist); } return 0;}