模拟退火,只能过hack点
查看原帖
模拟退火,只能过hack点
701221
Chr0n1CleC楼主2022/8/14 21:12
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#include<math.h>
#define N 10000009
#include<algorithm>
#define random std::random_shuffle

double ansx, ansy, ansr;

int n;

struct node
{
	double x, y;
}a[N];	

inline double max(double a, double b) {return a > b ? a : b;}

inline double Rand() {return 1.0 * rand() / RAND_MAX;}

inline double calc(double xx, double yy)
{
	double ret = 0;
	for (int i = 1;i <= n;i ++)
		ret = max(ret, (xx - a[i].x) * (xx - a[i].x) + (yy - a[i].y) * (yy - a[i].y));
	ret = sqrt(ret);
	if (ret < ansr)
		ansx = xx, ansy = yy, ansr = ret;
	return ret;
}

int main()
{
	srand(time(0));
	scanf("%d", &n);
	for (int i = 1;i <= n;i ++)
		scanf("%lf%lf", &a[i].x, &a[i].y);
	random(a + 1, a + 1 + n);
	int k = rand() * rand() % n + 1;
	ansx = a[k].x, ansy = a[k].y, ansr = calc(ansx, ansy);
	while (1.0 * clock() / CLOCKS_PER_SEC < 0.99)
	{
		for (int i = 1;i <= 5 && 1.0 * clock() / CLOCKS_PER_SEC < 0.99;i ++)
		{
			double T = 1e6, x = ansx, y = ansy, r = ansr;
			while (T > -1e6 && 1.0 * clock() / CLOCKS_PER_SEC < 0.99)
			{
				double nx = x + T * (Rand() * 2 - 1);
				double ny = y + T * (Rand() * 2 - 1);
				double f = calc(nx, ny) - r;
				if (exp(-f / T) > Rand())
					x = nx, y = ny, r = calc(x, y);
				T *= 0.999;
			}
		}
	}
	printf("%.2lf %.2lf %.2lf", ansx, ansy, ansr);
	
	return 0;
}

2022/8/14 21:12
加载中...