ACWING 3176. 星星还是树

原题链接

描述

在二维平面上有 \(n\) 个点，第 \(i\) 个点的坐标为 \((x_i,y_i)\)。

请你找出一个点，使得该点到这 \(n\) 个点的距离之和最小。

该点可以选择在平面中的任意位置，甚至与这 \(n\) 个点的位置重合。

思路

模拟退火模板题

代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e4+10;
#define pdd pair<double ,double>
#define x first
#define y second
pdd p[N];
int n; 
double ans=1e8;
double randn(double l,double r){
    return (double)rand()/RAND_MAX*(r-l)+l;
}
double dist(pdd a,pdd b){
    double dx=b.x-a.x;
    double dy=b.y-a.y;
    return sqrt(dx*dx+dy*dy);
}
void sa(){
    pdd cp(randn(0,10000),randn(0,10000));
    for(double t=10000;t>=1e-4;t*=0.99){
        pdd np=make_pair(randn(cp.x-t,cp.x+t),randn(cp.y-t,cp.y+t));
        double sn=0;
        for(int i=0;i<n;i++) sn+=dist(np,p[i]);
        ans=min(ans,sn);
        double sc=0;
        for(int i=0;i<n;i++) sc+=dist(cp,p[i]);
        double d=sn-sc;
        ans=min(ans,sc);
        if(exp((-1)*d/t)>randn(0,1)) cp=np;
    }
}
int main(){
    srand(time(NULL));
    cin>>n;
    for(int i=0;i<n;i++){
        scanf("%lf%lf",&p[i].x,&p[i].y);
    }
    for(int i=0;i<100;i++){
        sa();
    }
    printf("%.0lf",ans);
    return 0;
}