【bzoj3680】吊打XXX

2015.05.25 08:33 Mon | 36次阅读 | 旧日oi | 固定链接 | 源码

题目大意:给定n个质点,求重心。
题解
模拟退火裸题,照popoqqq大爷的程序写的。

我的程序

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define N 10010
using namespace std;
struct Point{
    double x,y,g;
}p[N],ans;
int n;
double minans=23333333333333333ll;
double dis(const Point &a,const Point &b)
{
    return sqrt(pow(a.x-b.x,2.0)+pow(a.y-b.y,2.0));
}
double jud(const Point &x)
{
    double ret=0;
    for(int i=1;i<=n;i++) ret+=p[i].g*dis(x,p[i]);
    if(ret<minans) minans=ret,ans=x;
    return ret;
}
double Rand()
{
    return rand()%1000/1000.0;  
}
void monitui_fire(double T)
{
    Point now=ans;
    while(T>0.01)
    {
        Point tmp;
        tmp.x=now.x+T*(Rand()*2-1);
        tmp.y=now.y+T*(Rand()*2-1);
        double dE=jud(now)-jud(tmp);
        if(dE>0||exp(dE/T)>Rand()) now=tmp;
        T*=0.993;
    }
    for(int i=1;i<=1000;i++)
    {
        Point tmp;
        tmp.x=ans.x+T*(Rand()*2-1);
        tmp.y=ans.y+T*(Rand()*2-1);
        jud(tmp);
    }
}
int main()
{
    cin>>n;
    srand(19981013);
    for(int i=1;i<=n;i++)
    {
        scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].g);
        ans.x+=p[i].x;ans.y+=p[i].y;
    }
    ans.x/=n;ans.y/=n;
    monitui_fire(100000);
    printf("%.3lf  %.3lf\n",ans.x,ans.y);
}```