|
做題之前：
令一個點到一個分身的距離為兩點間的幾何距離*這個分身的重力，則到所有分身的距離之和最小的點即為所求。
因此題各種參數(shù)實在太恐怖，使得模擬退火TLE/WA無數(shù)次。強烈建議此題更名為“吊打出題人”。
在此感謝網(wǎng)上的大神給了我們調(diào)參數(shù)的偉大參考！??！
吊打XXX C++代碼實現(xiàn)：
- #include <cmath>
- #include <cstdio>
- #include <cstring>
- #include <iostream>
- #include <algorithm>
- #define N 10010
- using namespace std;
- int n,x[N],y[N],w[N];double dis,ansx,ansy,xx,yy;
- double dist(double x1,double x2,double y1,double y2)
- {
- return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
- }
- int main()
- {
- cin>>n;
- for(int i=1;i<=n;i++)
- scanf("%d%d%d",&x[i],&y[i],&w[i]);
- double t=1000;
- for(int i=1;i<=n;i++)
- ansx+=x[i]*w[i],ansy+=y[i]*w[i];
- ansx/=n,ansy/=n;
- while(t>0.000000001)
- {
- xx=yy=0;
- for(int i=1;i<=n;i++)
- dis=dist(ansx,x[i],ansy,y[i]),
- xx+=(x[i]-ansx)*w[i]/dis,
- yy+=(y[i]-ansy)*w[i]/dis;
- ansx+=xx*t,ansy+=yy*t;
- t=t>0.5?t*0.5:t*0.98;
- }
- printf("%.3lf %.3lf\n",ansx,ansy);
- return 0;
- }
|
