「Luogu1337」[JSOI] 平衡点
题目描述
如图：有n个重物，每个重物系在一条足够长的绳子上。每条绳子自上而下穿过桌面上的洞，然后系在一起。图中X处就是公共的绳结。假设绳子是完全弹性的（不会造成能量损失），桌子足够高（因而重物不会垂到地上），且忽略所有的摩擦。
问绳结X最终平衡于何处。
注意：桌面上的洞都比绳结X小得多，所以即使某个重物特别重，绳结X也不可能穿过桌面上的洞掉下来，最多是卡在某个洞口处。
问绳结X最终平衡于何处。
注意：桌面上的洞都比绳结X小得多，所以即使某个重物特别重，绳结X也不可能穿过桌面上的洞掉下来，最多是卡在某个洞口处。
输入格式
文件的第一行为一个正整数n（1≤n≤1000），表示重物和洞的数目。接下来的n行，每行是3个整数：Xi.Yi.Wi，分别表示第i个洞的坐标以及第 i个重物的重量。(-10000≤x,y≤10000, 0<w≤1000 )
输出格式
你的程序必须输出两个浮点数（保留小数点后三位），分别表示处于最终平衡状态时绳结X的横坐标和纵坐标。两个数以一个空格隔开。
样例输入
3
0 0 1
0 2 1
1 1 1
样例输出
0.577 1.000
题解
设桌子的高度为h0，每根绳子长l0[i]，在座子上的长度为a[i]
那么E=Σw[i]*(h0-l0[i])+Σw[i]*a[i]
只要最小化Σw[i]*a[i]即可
所以问题转化为广义费马点
|
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 |
#include<iostream> #include<cstdio> #include<cmath> using namespace std; int n; double ansx,ansy; struct data{double x,y;int w;}p[1005]; inline double sqr(double x){return x*x;} inline double dis(double x,double y,data p) { return sqrt(sqr(x-p.x)+sqr(y-p.y)); } void hillclimb() { double t=10000,x,y; for(int i=1;i<=n;i++) ansx+=p[i].x*p[i].w,ansy+=p[i].y*p[i].w; ansx/=n;ansy/=n; while(t>0.0000001) { x=y=0; for(int i=1;i<=n;i++) { x+=(p[i].x-ansx)*p[i].w/dis(ansx,ansy,p[i]); y+=(p[i].y-ansy)*p[i].w/dis(ansx,ansy,p[i]); } ansx+=x*t;ansy+=y*t; t*=0.99; } printf("%.3lf %.3lf",ansx,ansy); } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lf%lf%d",&p[i].x,&p[i].y,&p[i].w); hillclimb(); return 0; } |
计数器 9320923
OI 课件=>
OI 课件=>
谢谢！
请问：ansx+=x*t，为啥是乘t
x是水平合外力，t是精度误差，那么这个式子怎么理解？
这是模拟退火丫。。
图挂了
没办法。。。