题意

题目描述

如图：有n个重物，每个重物系在一条足够长的绳子上。每条绳子自上而下穿过桌面上的洞，然后系在一起。图中X处就是公共的绳结。假设绳子是完全弹性的（不会造成能量损失），桌子足够高（因而重物不会垂到地上），且忽略所有的摩擦。

问绳结X最终平衡于何处。

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

注意：桌面上的洞都比绳结X小得多，所以即使某个重物特别重，绳结X也不可能穿过桌面上的洞掉下来，最多是卡在某个洞口处。

LG1337 [JSOI2004]平衡点 / 吊打XXX 随笔

输入输出格式

输入格式：

文件的第一行为一个正整数n（1≤n≤1000），表示重物和洞的数目。接下来的n行，每行是3个整数：Xi.Yi.Wi，分别表示第i个洞的坐标以及第 i个重物的重量。(-10000≤x,y≤10000, 0<w≤1000 )

输出格式：

你的程序必须输出两个浮点数（保留小数点后三位），分别表示处于最终平衡状态时绳结X的横坐标和纵坐标。两个数以一个空格隔开。

输入输出样例

输入样例#1： 复制 
3
0 0 1
0 2 1
1 1 1
输出样例#1： 复制 
0.577 1.000

说明

[JSOI]

分析

参照FlashHu的题解。

这道题还真和能量有点关系。达到平衡稳态的时候，物体的总能量应该是最小的。而总的能量来源于每个物体的重力势能之和。要想让某个物体势能减小，那就让拉着它的绳子在桌面下方的长度尽可能的长，也就是桌面上的要尽可能短。由此看来，某个物体的势能与桌面上的绳子的长度、物体重量都成正比。

于是，为了找到平衡点，我们要找一个点使得\(\sum^n_{i=1}d_i∗w_i\)最小（\(d_i\)为i点到该点的距离）。我不明白既然绳子足够长，为什么会有这种重力势能的定义。并且按道理这标量和是错的。

函数已经求出来了，接下来就是正常的模拟退火过程。注意一些细节就好了。

首先，初始解可以设成坐标平均数，可以更接近正解

解变动值最好随机两个值，Δx和Δy。随机变动距离和角度可能常数有点大。

然后就开始退火……感觉这算法就玄学。

代码

时间复杂度无法分析，采用卡时限做法。

#include<bits/stdc++.h>
#define rg register
#define il inline
#define co const
template<class T>il T read(){
    rg T data=0,w=1;rg char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') w=-1;ch=getchar();}
    while(isdigit(ch)) data=data*10+ch-'0',ch=getchar();
    return data*w;
}
template<class T>il T read(rg T&x) {return x=read<T>();}
typedef long double ld;
using namespace std;

co int N=1e3+1;
co ld D=0.97,eps=1e-14;
ld x[N],y[N],w[N];
int n;
ld calc(ld x0,ld y0){
    ld res=0;
    for(int i=1;i<=n;++i)
        res+=sqrt(pow(x[i]-x0,2)+pow(y[i]-y0,2))*w[i];
    return res;
}
int main(){
    ld bx=0,by=0,best;
    read(n);
    for(int i=1;i<=n;++i)
        bx+=read(x[i]),by+=read(y[i]),read(w[i]);
    best=calc(bx/=n,by/=n);
    srand(time(0));
    for(ld ans,x0,y0;clock()<CLOCKS_PER_SEC*0.9;){
        ans=best,x0=bx,y0=by;
        for(ld T=1e5,res,x1,y1;T>eps;T*=D){
#define RD T*(rand()*2-RAND_MAX)
            res=calc(x1=x0+RD,y1=y0+RD);
            if(best>res) best=res,bx=x1,by=y1;
            if(ans>res||exp((ans-res)/T)>(long double)rand()/RAND_MAX) ans=res,x0=x1,y0=y1;
        }
    }
    printf("%.3Lf %.3Lf\n",bx,by);
    return 0;
}

再分析

受洛谷题解启发

我们可以确定一个原点，将所有的力在这个原点上正交分解，最终我们可以得到所有的力的一个合力，而真正的平衡点一定在合力所指向的方向上

我想了一下悬挂法找重心。但是由于这题的力方向在悬挂点移动的时候会改变，所以不能直接找两条线求交。

偏移量是一个大概位置，那么每次改变步长然后移动就行了。玄学调参。

再代码

#include<bits/stdc++.h>
#define rg register
#define il inline
#define co const
template<class T>il T read(){
    rg T data=0,w=1;rg char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') w=-1;ch=getchar();}
    while(isdigit(ch)) data=data*10+ch-'0',ch=getchar();
    return data*w;
}
template<class T>il T read(rg T&x) {return x=read<T>();}
typedef long long ll;
using namespace std;

co double eps=1e-12;
typedef struct Point{double x,y;}Vector;
bool operator!=(co Point&a,co Point&b) {return abs(a.x-b.x)>eps||abs(a.y-b.y)>eps;}
Vector operator+(co Vector&u,co Vector&v) {return (Vector){u.x+v.x,u.y+v.y};}
Vector operator-(co Vector&u,co Vector&v) {return (Vector){u.x-v.x,u.y-v.y};}
Vector operator*(co Vector&u,double k) {return (Vector){u.x*k,u.y*k};}
Vector operator/(co Vector&u,double k) {return (Vector){u.x/k,u.y/k};}
double cross(co Vector&u,co Vector&v) {return u.x*v.y-u.y*v.x;}
double dot(co Vector&u,co Vector&v) {return u.x*v.x+u.y*v.y;}
double length(co Vector&u) {return sqrt(dot(u,u));}
Vector normal(co Vector&u) {return u/length(u);}
Point intersection(co Point&a,co Vector&u,co Point&b,co Vector&v){
    return a+u*cross(v,a-b)/cross(u,v);
}

co int N=1e3+1;
int n,w[N];
Point p[N],ans;
int main(){
    read(n);
    for(int i=1;i<=n;++i){
        read(p[i].x),read(p[i].y),read(w[i]);
        ans=ans+p[i]*w[i],w[0]+=w[i];
    }
    ans=ans/w[0];
    double t=1e4;
    for(Point a,b,u,v;clock()<CLOCKS_PER_SEC*0.9;t*=0.95){
        a=ans-(Vector){t*eps,t*eps},b=ans+(Vector){t*eps,t*eps};
        u=(Vector){0,0},v=(Vector){0,0};
        for(int i=1;i<=n;++i){
            if(p[i]!=a) u=u+normal(p[i]-a)*w[i];
            if(p[i]!=b) v=v+normal(p[i]-b)*w[i];
        }
        if(abs(cross(u,v))>eps) ans=intersection(a,u,b,v);
    }
    printf("%.3lf %.3lf",ans.x,ans.y);
    return 0;
}
扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄