模拟退火90pts WA #2求条
查看原帖
模拟退火90pts WA #2求条
963247
Slient_QwQ楼主2024/4/3 23:51

rt

/*Code By Manipula*/
#include <bits/stdc++.h>
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
#define fi first
#define sc second
#define lb lower_bound
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define Debug(fmt, arg...) fprintf(stderr, fmt, ##arg)
#define DEBUG() debug("In Function [%s] Line %d\n", __FUNCTION__, __LINE__) 

const int N = 1e3 + 5;

int x[N], y[N], r[N], p[N], q[N];
int n, m, R, ans;

double ansx, ansy;

int rnd() {
	return rand() * 2 - RAND_MAX;
}

double dist(double a, double b, double c, double d) {
	return sqrt((a - c) * (a - c) + (b - d) * (b - d));
}

int get(double X, double Y) {
	int res = 0;
	
	double _r = R;
	
	for (int i = 1; i <= n; i++)
		_r = std::min(_r, dist(X, Y, x[i], y[i]) - r[i]);
			
	for (int i = 1; i <= m; i++)
		if (dist(X, Y, p[i], q[i]) <= _r)
			res++;
	
	return res;
}

void SA() {
	double T = 3000, delta = 0.9972;
	
	while (T > 1e-15) {		
		double X = ansx + rnd() * T, Y = ansy + rnd() * T;
		int now = get(X, Y), E = ans - now;
		
		// printf("%.3lf  %.3lf  %lld\n", X, Y, now);
		
		if (E < 0)ansx = X, ansy = Y, ans = now;
		else if (exp(-E / T) > rand())ansx = X, ansy = Y;
		
		T *= delta;
	}
}

signed main() {
	// freopen(".in", "r", stdin);
	// freopen(".out", "w", stdout);
	
	scanf("%lld%lld%lld", &n, &m, &R);
	for (int i = 1; i <= n; i++)
		scanf("%lld%lld%lld", &x[i], &y[i], &r[i]);
	for (int i = 1; i <= m; i++)
		scanf("%lld%lld", &p[i], &q[i]);
	
	for (int i = 1; i <= m; i++)
		ansx += p[i], ansy += q[i];
	
	ansx /= m, ansy /= m, ans = get(ansx, ansy);
		
	SA();
	
	printf("%lld", ans);
	
	return 0;
}
2024/4/3 23:51
加载中...