题目描述
农历新年马上就要到了,奶牛们计划举办一次聚会庆祝新年的到来。但是,奶牛们并不喜欢走太远的路,这会给他们的聚会带来消极情绪,当一头奶牛的消极指数为Wi,他参加聚会所需行走的距离为si,那么他就会给聚会带来Si*Wi的消极情绪。所有奶牛所在位置都在一条直线上,已知所有奶牛的坐标和消极指数,求如何确定聚会地点,使得所有奶牛给聚会带来的消极情绪之和最小,输出消极情绪之和的最小值。
输入
第一行包含一个整数 Ca(Ca<=20) ,表示有 Ca 组测试数据。
对于每组测试数据:第一行包含一个整数n(1<=n<=50000) ,表示奶牛的数量。接下来 n 行每行包含两个浮点数Si和wi (-106<=Si<=106, 0<Wi<15)。
输出
对于每组测试数据,输出 "Case #c: ans" ,其中c表示测试数据编号,ans表示消极情绪之和的最小值,结果四舍五入为一个整数。
样例输入
1 5 0.9 2 1.4 4 3.1 1 6.2 1 8.3 2
样例输出
Case #1: 300
三分,裸的,可以自己用定义证一下凸函数加凸函数等于凸函数
```c++ #include
for(pla=0.9;pla<=8.3;pla+=0.1)
cout<<pla<<":"<<ans(pow(abs(0.9-pla),3)*2+pow(abs(1.4-pla),3)*4+pow(abs(3.1-pla),3)*13+pow(abs(6.2-pla),3)*1+pow(abs(8.3-pla),3)*2)<<endl;
*/
cin>>T;
for(int I=1;I<=T;I++){
memset(s,0,sizeof(s));
memset(w,0,sizeof(w));
scanf("%d",&n);
ld l=1e7,r=-1e7;
for(int i=1;i<=n;i++){
scanf("%lf%lf",&s[i],&w[i]);
//cin>>s[i]>>w[i];
//cout<<s[i]<<' '<<w[i]<<endl;
l=min(s[i],l);
r=max(s[i],r);
}
//cout<<l<<" "<<r<<endl;
//cout<<r-l<<endl;
while(r-l>0.00001){
ld m1=l+(r-l)/3.0;
ld m2=r-(r-l)/3.0;
if(smstp(m1)<smstp(m2)){
r=m2;
}
else{
l=m1;
}//cout<<(int)l<<" "<<(int)r<<endl;
}
cout<<"Case #"<<I<<": "<<ans(smstp(l))<<endl;
}
return 0;
}```