3680: 吊打XXX

链接

思路：

　　模拟退火。

代码：

跑的特别慢。。。

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<cctype>

 #include<cmath>

 using namespace std;

 const int N = ;

 struct Node{

     double x,y,w;

 }d[N],ans;

 int n;

 double minans = 1e18;

 double dis(Node a,Node b) {

     return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));

 }

 double check(Node p) {

     double ret = ;

     for (int i=; i<=n; ++i)

         ret += d[i].w*dis(p,d[i]);

     if (ret < minans)

         ans = p,minans = ret;

     return ret;

 }

 double Rand() {

     return rand()%/1000.0;

 }

 void SA() {

     double T = ;

     Node now = ans;

     while (T > 0.001) {

         Node nxt;

         nxt.x = now.x+T*(Rand()*2.0-1.0);

         nxt.y = now.y+T*(Rand()*2.0-1.0);

         double Delta = check(now)-check(nxt);

         if (Delta >  || exp(Delta/T)>Rand()) now = nxt;

         T *= 0.993;

     }

     for (int i=; i<=; ++i) {

         Node nxt;

         nxt.x = ans.x+T*(Rand()*2.0-1.0);

         nxt.y = ans.y+T*(Rand()*2.0-1.0);

         check(nxt);

     }

 }

 int main() {

     srand();

     scanf("%d",&n);

     ans.x = ans.y = ;

     for (int i=; i<=n; ++i) {

         scanf("%lf%lf%lf",&d[i].x,&d[i].y,&d[i].w);

         ans.x += d[i].x;

         ans.y += d[i].y;

     }

     ans.x /= (double)n;

     ans.y /= (double)n;

     SA();

     printf("%.3lf %.3lf",ans.x,ans.y);

     return ;

 }