模拟退火求调
查看原帖
模拟退火求调
519384
Link_Cut_Y楼主2022/3/13 16:32
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdio>
#include <ctime>
#include <cmath>

#define x first
#define y second

using namespace std;

typedef pair<double, double> PDD;
const int N = 15, M = 1010;
struct Buildings
{
    double x, y;
    double r;
}buildings[N];

PDD enemy[M], s;
int n, m;
double R;
int res = 0;

double rand(double l, double r)
{
	return (double)rand() / RAND_MAX * (r - l) + l;
}

double get_dist(PDD a, PDD b)
{
	double dx = a.x - b.x;
	double dy = a.y - b.y;
	return sqrt(dx * dx + dy * dy);
}

int calc(PDD a)
{
	double r = R;
	for (int i = 0; i < n; i ++ )
		r = min(r, get_dist(a, {buildings[i].x, buildings[i].y}) - buildings[i].r);
	
	int cnt = 0;
	
	for (int i = 0; i < m; i ++ )
		if (get_dist(a, enemy[i]) <= r)
			cnt ++ ;
			
	res = max(res, cnt);
	
	return cnt;
}

void sumilate_anneal()
{
    PDD u = s;
    for (double t = 2e4; t >= 1e-4; t *= 0.99)
    {
        int x = calc(u);
        PDD v(rand(u.x - t, u.x + t), rand(u.y - t, u.y + t));
        int y = calc(v);
        int delta = y - x;
        if (exp(-delta / t) < rand(0, 1)) u = v;
    }
}

int main()
{
    scanf("%d%d%lf", &n, &m, &R);
    
    for (int i = 0; i < n; i ++ )
        scanf("%lf%lf%lf", &buildings[i].x, &buildings[i].y, &buildings[i].r);
        
    for (int i = 0; i < m; i ++ )
        scanf("%lf%lf", &enemy[i].x, &enemy[i].y), s.x += enemy[i].x, s.y += enemy[i].y;
    
    s.x /= m, s.y /= m;
    
    while ((double)clock() / CLOCKS_PER_SEC < 0.8) sumilate_anneal();
    
    printf("%d\n", res);
    
    return 0;
}
2022/3/13 16:32
加载中...