旋转卡壳 + 模拟退火 全TLE
查看原帖
旋转卡壳 + 模拟退火 全TLE
701221
Chr0n1CleC楼主2022/8/15 18:57
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#include<math.h>
#define N 1000009
#include<algorithm>
#include<iostream>
using namespace std;

double ansx, ansy, ansr;

int n;

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

struct node
{
	double x, y;
	node()
	{
		x = 0, y = 0;
	}
}a[N], s[N];
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 top;

inline double h(node a, node b)
{
	return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

inline double cross(node A, node B, node C, node D)
{
	return (B.x - A.x) * (D.y - C.y) - (B.y - A.y) * (D.x - C.x);
}

inline bool cmp(node A, node B)
{
	int x = cross(a[1], A, a[1], B);
	if (x < 0)
		return false;
	if (x > 0)
		return true;
	return h(A, a[1]) < h(B, a[1]); 
}

int main()
{
	srand(time(0));
	scanf("%d", &n);
	for (int i = 1;i <= n;i ++)
	{
		scanf("%lf%lf", &a[i].x, &a[i].y);
		if ((a[i].y < a[1].y) || (a[i].y == a[1].y && a[i].x < a[1].x))
			swap(a[i], a[1]);
	}
	sort(a + 2, a + 1 + n, cmp);
	s[++ top] = a[1];
	for (int i = 2;i <= n;i ++)
	{
		while (top > 1 && cross(s[top - 1], s[top], s[top], a[i]) <= 0)
			top --;
		s[++ top] = a[i];
	}
	s[top + 1] = a[1];
	double ans = 0;
	node A, B;
	int j = 2;
	for (int i = 1;i <= top && top;i ++)
	{
		while (cross(s[i], s[i + 1], s[i + 1], s[j]) <= 
			   cross(s[i], s[i + 1], s[i + 1], s[j + 1]))
			j = (j == top) ? 1 : j + 1;
//		ans = max(ans, max(h(s[i], s[j]), h(s[i + 1], s[j])));
		if (h(s[i], s[j]) > ans)
			ans = h(s[i], s[j]), A = s[i], B = s[j];
		if (h(s[i + 1], s[j]) > ans)
			ans = h(s[i + 1], s[j]), A = s[i + 1], B = s[j];
	}
	ansx = (A.x + B.x) / 2;
	ansy = (A.y + B.y) / 2;
	ansr = calc(ansx, ansy);
	while (1.0 * clock() / CLOCKS_PER_SEC < 0.4)
	{
		double T = 600000, x = ansx, y = ansy, r = ansr;
		while (T > -1e12)
		{
			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.997;
		}
	}
	printf("%.2lf %.2lf %.2lf", ansx, ansy, ansr);
	
	return 0;
}

2022/8/15 18:57
加载中...