题目大意:有$n$个重物,每个重物系在一条绳子上。所有绳子系在一起,问绳结最终平衡于何处。

题解:$NOIP$前学学模拟退火,但发现我脸好黑啊。。。

卡点:脸黑

C++ Code:

#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <ctime>
#define maxn 1010
int Tim = 22;
const int __Tim = 2000;
const double eps = 1e-6, __eps = 1e-4;
const double k = 0.995, Temp = 500;
inline double abs(double a) {return a < 0 ? -a : a;}
inline double dis(double x, double y) {return sqrt(x * x + y * y);}
inline double RAND() {return static_cast<double> (rand()) / RAND_MAX;} int n;
struct point {
double x, y, w;
inline void operator += (const point &rhs) {
x += rhs.x;
y += rhs.y;
w += rhs.w;
}
inline void operator /= (const double &rhs) {
x /= rhs;
y /= rhs;
}
} s[maxn], ans; inline double calc(point &lhs) {
lhs.w = 0;
for (register int i = 1; i <= n; i++) {
lhs.w += dis(lhs.x - s[i].x, lhs.y - s[i].y) * s[i].w;
}
return lhs.w;
}
void SA() {
double T = Temp, del;
point now = ans, nxt;
while (T > eps) {
nxt.x = now.x + T * (2 * RAND() - 1);
nxt.y = now.y + T * (2 * RAND() - 1);
del = calc(nxt);
if ((del < now.w) || exp((now.w - nxt.w) / T) > RAND()) now = nxt;
if (del < ans.w) ans = nxt;
T *= k;
}
int Tim = __Tim;
now = ans;
T = __eps;
while (Tim --> 0) {
nxt.x = now.x + T * (2 * RAND() - 1);
nxt.y = now.y + T * (2 * RAND() - 1);
del = calc(nxt);
if ((del < now.w) || exp((now.w - nxt.w) / T) > RAND()) now = nxt;
if (del < ans.w) ans = nxt;
}
} int main() {
srand(20040826);
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%lf%lf%lf", &s[i].x, &s[i].y, &s[i].w);
ans += s[i];
}
ans /= n; calc(ans);
while (Tim --> 0) SA();
printf("%.3lf %.3lf\n", ans.x, ans.y);
return 0;
}

  

最新文章

  1. C#基础知识汇总
  2. wangEditor ie9 表单上传图片
  3. AdaBoosting 3
  4. Velocity魔法堂系列二:VTL语法详解
  5. C Primer Plus(第五版)6
  6. 捕获JSON 解析错误
  7. JDBC_mysql---防sql注入,存储图片
  8. tar.xz文件怎样解压
  9. poemel 端口作用
  10. struts体系结构
  11. excel 合并多个文件
  12. 微信小程序实操-image height:auto问题,url地址报错,“不在以下合法域名列表中”问题等
  13. MapReduce执行流程及程序编写
  14. 通过全备+binlog_server同步恢复被drop的库或表
  15. flask设置cookie,设置session,模拟用户认证、模拟管理后台admin、模拟用户logout
  16. 4、Ansible(tags、roles)
  17. 【问题解决方案】Keras手写数字识别-ConnectionResetError: [WinError 10054] 远程主机强迫关闭了一个现有的连接
  18. 图片按钮(imageButton)
  19. KMP---POJ 3461 Oulipo
  20. 微信小程序 的文字复制功能如何实现?

热门文章

  1. I/O流、ZIP文档
  2. 微信小程序关于tabbar点击切换数据不刷新问题
  3. PHP-入门指引1
  4. flask钩子
  5. Hbase数据IO
  6. EAS_Table
  7. 【APUE】Chapter5 Standard I/O Library
  8. springmvc基础篇—掌握三种控制器
  9. 「暑期训练」「基础DP」 Piggy-Bank (HDU-1114)
  10. 使用git创建分支