好像是第一次接触这个好像叫 “膜膜膜膜你退火算法” 关键词:计算几何  模拟退火  搜索 相关题目: [BZOJ3680] 吊打XXX

Description

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

Input&Output

Input 输入第一行为一个正整数 ,表示gty的数目。 接下来n行,每行三个整数 ,表示第 ii 个gty的横坐标,纵坐标和重力。 对于20%的数据,gty排列成一条直线。 对于50%的数据, 。 对于100%的数据,

Output 输出1行两个浮点数(保留到小数点后3位),表示最终 xx 的横、纵坐标。

Sample Input

3
0 0 1
0 2 1
1 1 1

Sample Output

0.577 1.000

分析及解决

学习 模拟退火算法 做的模板题。怎么感觉学了奇技淫巧高端骗分技巧。。。 注意一下下面点就好了:

  1. 原题可以转化为当 取最小值时的 α\alpha 的坐标
  2. 除了计算得到更优秀的点外,还需要添加随机情况更新节点     当前\Rightarrow目标
  3. 最后注意乱搞微调确定的点 α\alpha 的坐标

2018.04.19


诶,之前说的好像...... (此处省略10086字)。正解应该是下面这样的: 我们可以先枚举一个平衡点,然后将所有的力在此处进行 正交分解 。如果整个点不为平衡点,那么最终一定会有一个多余的合力。并且平衡点必定在合力方向。 那么我们只需要在每一步设置一个移动距离 ss 。 正交分解 -> 移动 重复做就可以了。 注意一点:因为每一次移动都期望向平衡点靠近,所以移动距离 ss 可以视情况减小,以趋于稳定。

2018.04.20

AC代码

啊?模拟退火

Memory: 1068 kb / Time: 7596 ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++i)
#define FIRE(x) (x*=0.99)
const double eps=1e-4, pi=acos(-1);

struct Node{
double x, y, w;
Node(){}
Node(double _x, double _y) {x=_x, y=_y;}
inline void operator += (const Node &rhs) {
x += rhs.x, y += rhs.y;
}
inline void operator /= (const int k) {
x /= k, y /= k;
}
}p[10020];
Node now, ans;
double sta=1e17;

inline double rnd() {
return ( rand() % 1000 + 1) / 1000.0;
}

inline double dist(Node A, Node B) {
return sqrt( (A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y) );
}

int n;

inline double state(Node P) {
double res=0.0;
rep(i,1,n) res += dist(P,p[i]) * p[i].w;
if(res < sta) sta=res, ans=P;
return res;
} //点 P 的 Σdis(P,i) * Wi 的值

int main(){
srand(10086);
scanf("%d", &n);
rep(i,1,n) scanf("%lf%lf%lf", &p[i].x, &p[i].y, &p[i].w), now+=p[i];
now /= n;

double T=100000.0, alpha, sub;
while(T > eps) {
alpha = 2.0 * pi * rnd();
Node tmp(now.x + T * cos(alpha), now.y + T * sin(alpha));
sub = state(now) - state(tmp);
if(sub >= 0 || exp(sub/T) >= rnd() ) now=tmp; // 当前解不如目标 + 随机
FIRE(T); //模拟退火
}
T = 0.001;
rep(i,1,2333) {
alpha = 2.0 * pi * rnd();
Node tmp(ans.x + T * cos(alpha) * rnd(), ans.y + T * sin(alpha) * rnd());
state(tmp);
} //乱搞 (微调)
printf("%.3lf %.3lf\n", ans.x, ans.y);
}

哦!正交分解

Memory: 1056 kb / Time: 804 ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <cstdio>
#include <cmath>
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++i)
const double eps=1e-5;

struct Node {
double x, y, w;
Node() {x=y=w=0;}
}p[10005];

int n;
Node ans, now;
bool dirx=1, diry=1;

inline double dist(Node A, Node B) {
return sqrt( (A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y));
}

inline void move(double s) {
double X, Y, dis, F;
X=Y=0;
rep(i,1,n) {
dis = dist(ans, p[i]);
if(dis == 0) continue; //重合
X += p[i].w * (p[i].x - ans.x) / dis;
Y += p[i].w * (p[i].y - ans.y) / dis;
} //正交分解
F = sqrt(X*X + Y*Y); //合力

ans.x += s * (X / F);
ans.y += s * (Y / F); //将原点在合力方向上位移一定距离
}
int main() {
scanf("%d", &n);
rep(i,1,n)
scanf("%lf%lf%lf", &p[i].x, &p[i].y, &p[i].w);

double s = 20000;
while(1) {
now = ans;
move(s);

if(fabs(now.x-ans.x)<eps && fabs(now.y-ans.y)<eps) break;

if ((dirx != (ans.x>now.x)) || (diry != (ans.y>now.y))) {
dirx = ans.x > now.x;
diry = ans.y > now.y;
s = s * 0.9;
} // 移动方向变化
}
printf("%.3f %.3f\n", ans.x, ans.y);
}