题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3680
题意：对于一个节点，有 n 个来自于 x[i],y[i]，大小为 w[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 40 41 42 43 44 |
#include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #define eps 1e-8 #define N 10010 using namespace std; int n; struct point { double x,y,w; }a[N]; double ansx,ansy; double dis(point a,point b) {return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));} void climb() { double x,y,t=233; for(int i=1;i<=n;i++) ansx+=a[i].x*a[i].w,ansy+=a[i].y*a[i].w; ansx/=n,ansy/=n; while(t>eps) { x=y=0; point ans;ans.x=ansx,ans.y=ansy; for(int i=1;i<=n;i++) { double d=dis(ans,a[i]); x+=(a[i].x-ansx)*a[i].w/d; y+=(a[i].y-ansy)*a[i].w/d; } ansx+=x*t,ansy+=y*t; if(t>0.5)t*=0.5; else t*=0.97; } printf("%.3lf %.3lf",ansx,ansy); } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lf %lf %lf",&a[i].x,&a[i].y,&a[i].w); climb(); } |
Comments | NOTHING