刚学模拟退火,wa
查看原帖
刚学模拟退火,wa
342584
流夏的美楼主2020/9/5 20:38
#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#define maxn 1005
#define mod 2 * 1000 - 1
using namespace std;

int n, m;
double r;
int ans;
int nowx, nowy;
int ax, ay;
double bx[maxn], by[maxn], br[maxn];
double qx[maxn], qy[maxn];
double delta = 0.997;
double sumx, sumy;

double dis(double x1, double y1, double x2, double y2) {
	return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

int slove(double x, double y) {
	double ar = r;
	int s = 0;
	for(int i = 1; i <= n; ++i)
		ar = min(ar, dis(x, y, bx[i], by[i]));
	for(int i = 1; i <= m; ++i)
		if(dis(x, y, qx[i], qy[i]) <= ar) ++s;
	return s; 
}

void SA() {
	double ansx = ax, ansy = ay;
	double temp = 2614;
	while(temp > 1e-14) {
		double nowx = ansx + ( (rand() << 1) - RAND_MAX) * temp;
		double nowy = ansy + ( (rand() << 1) - RAND_MAX) * temp;
		int s = slove(nowx, nowy);
		if(ans < s) {
			ansx = nowx, ansy = nowy;
			ax = nowx, ay = nowy;
			ans = s;
		}
		else if(exp(-delta / temp) * RAND_MAX < rand()) {
			ansx = nowx, ansy = nowy;
		}
		temp *= delta;
	}
}

void run() {
	ax = sumx / m, ay = sumy / m;
	while(double(clock()) / CLOCKS_PER_SEC <= 0.85) SA();
}

int main() {
	srand(time(0));
	scanf("%d %d %lf", &n, &m, &r);
	for(int i = 1; i <= n; ++i) 
		scanf("%d %d %d", &bx[i], &by[i], &br[i]);
	for(int i = 1; i <= m; ++i) {
		scanf("%d %d", &qx[i], &qy[i]);
		sumx += qx[i], sumy += qy[i];
	}	
	run();
	printf("%d", ans);
}

实在是找不出来哪里错了,样例都没过/kk

2020/9/5 20:38
加载中...