BZOJ3680 JSOI2004 平衡点 - 随机/近似算法
2024-09-02 00:37:30
迭代乱搞了下就过了……
#include <bits/stdc++.h>
using namespace std; double x[],y[],w[];
double xm,ym,wt,k,lambda=0.9;
int n; const double ox[]={,,,-,},oy[]={,,,,-}; double calc(double xw,double yw){
double ans=;
for(int i=;i<=n;i++)
ans+=sqrt((xw-x[i])*(xw-x[i])+(yw-y[i])*(yw-y[i]))*w[i];
return ans;
} int main() {
cin>>n;
for(int i=;i<=n;i++)
cin>>x[i]>>y[i]>>w[i],
xm+=x[i]*w[i],
ym+=y[i]*w[i],
k=max(k,max(abs(x[i]),abs(y[i]))),
wt+=w[i];
xm/=wt;
ym/=wt; k*=0.1; double z=,oz=-1e+; while(k>=0.0001) {
//printf("%.3f %.3f k=%.4f\n",xm,ym,k);
oz=z;
double minopt=1e+;
int opt=;double tmp;
for(int i=;i<=;i++) { tmp=calc(xm+ox[i]*k,ym+oy[i]*k);
if(tmp<minopt)
minopt=tmp, opt=i;
}
xm+=ox[opt]*k, ym+=oy[opt]*k;
z=tmp;
k*=lambda;
} printf("%.3f %.3f\n",xm,ym);
}
最新文章
- 第二章Java基础之标识符
- css选择器优先级全解析
- JDBC之PreparedStatement模糊查询
- 常用Git命令汇总
- Excel几个常用操作
- uva 11427 - Expect the Expected(概率)
- 如何使用Android中的OpenGL ES媒体效果
- doubango(3)--协议栈的启动过程
- 201521123060 《Java程序设计》第12周学习总结
- RobotFramework下的http接口自动化Get Response Status 关键字的使用
- html 中 xmp标记
- mac 连接linux服务器,用scp命令实现本地文件与服务器文件之间的互相传输
- 【Hibernate】Unable to locate appropriate constructor on class原因分析
- python模块学习之hashlib模块学习
- PHP遍历二叉树
- 利用iptables防止ssh暴力破解和控制网速
- 6.装配Bean基于注解
- 业务-----添加Service常用逻辑
- 8.Thread的join方法
- 【转】Unity3D的LightProbe动态光探头用法介绍