BZOJ3680 吊打XXX

3680: 吊打XXX

Time Limit: 10 Sec  Memory Limit: 128 MBSec  Special Judge

Description

gty又虐了一场比赛，被虐的蒟蒻们决定吊打gty。gty见大势不好机智的分出了n个分身，但还是被人多势众的蒟蒻抓住了。蒟蒻们将
n个gty吊在n根绳子上，每根绳子穿过天台的一个洞。这n根绳子有一个公共的绳结x。吊好gty后蒟蒻们发现由于每个gty重力不同，绳
结x在移动。蒟蒻wangxz脑洞大开的决定计算出x最后停留处的坐标，由于他太弱了决定向你求助。
不计摩擦，不计能量损失，由于gty足够矮所以不会掉到地上。

Input

输入第一行为一个正整数n(1<=n<=10000)，表示gty的数目。
接下来n行,每行三个整数xi，yi，wi，表示第i个gty的横坐标，纵坐标和重力。
对于20%的数据，gty排列成一条直线。
对于50%的数据，1<=n<=1000。
对于100%的数据，1<=n<=10000,-100000<=xi,yi<=100000

Output

输出1行两个浮点数（保留到小数点后3位），表示最终x的横、纵坐标。

Sample Input

3
0 0 1
0 2 1
1 1 1

Sample Output

0.577 1.000

---

AC+1

模拟退火，爬山也可以。

---

正解：

#include<bits/stdc++.h>
using namespace std;
template <class _T> inline void read(_T &_x) {
    int _t; bool flag = false;
    while ((_t = getchar()) != '-' && (_t < '0' || _t > '9')) ;
    if (_t == '-') _t = getchar(), flag = true; _x = _t - '0';
    while ((_t = getchar()) >= '0' && _t <= '9') _x = _x * 10 + _t - '0';
    if (flag) _x = -_x;
}
using namespace std;
const int maxn = 10010;
const double Tmin = 1e-3;
struct Point {
    double x, y;
}p[maxn];
inline double dis(Point a, Point b) {
    return hypot(a.x - b.x, a.y - b.y);
}
int n, w[maxn];
double calc(Point P) {
    double ret = 0;
    for (int i = 1; i <= n; ++i)
        ret += dis(P, p[i]) * w[i];
    return ret;
}
double getr() {return (double)rand() / RAND_MAX; }
int main() {
    //freopen();
    //freopen();
    //srand(time(NULL));
    read(n);
    Point cur, to;
    cur.x = cur.y = 0;
    double ori_v, to_v;
    for (int i = 1, x, y; i <= n; ++i) {
        read(x), read(y), read(w[i]);
        p[i].x = x, p[i].y = y;
        cur.x += p[i].x, cur.y = p[i].y;
    }
    double T = 100000;
    cur.x /= n, cur.y /= n, ori_v = calc(cur);
    while (T > Tmin) {
        to.x = cur.x + (getr() * 2 - 1) * T;
        to.y = cur.y + (getr() * 2 - 1) * T;
        to_v = calc(to);
        if (to_v < ori_v || exp((ori_v - to_v) * 1e4 / T) > getr()) {
            cur = to, ori_v = to_v;
        }
        T = T * 0.98;
    }
    printf("%.3lf %.3lf
", cur.x, cur.y);
    return 0;
}

不是我说的：

#include <cstdio>
int main() {puts("nan nan");}