2018 ACM-ICPC 南京 D Country Meow
题意：
裸的最小球覆盖的半径
解题思路：
往距离当前点最远点跳的模拟退火，又好想又方便，同样一份代码但是poj2069死活过不去，一开始以为就我这样..后来到网上查了下这题的代码，改一改往poj一贴，全都wa了...没一个能活的...总感觉应该是poj2069的数据有点离谱，大概不是我的问题吧...大概
又写了下三分的写法
代码
#include <bits/stdc++.h>
using namespace std;
// freopen("k.in", "r", stdin);
// freopen("k.out", "w", stdout);
// clock_t c1 = clock();
// std::cerr << "Time:" << clock() - c1 <<"ms" << std::endl;
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#define de(a) cout << #a << " = " << a << endl
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define per(i, a, n) for (int i = n; i >= a; i--)
#define ls ((x) << 1)
#define rs ((x) << 1 | 1)
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<char, char> PCC;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
#define inf 0x3f3f3f3f
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll MAXN = 2e5 + 7;
const ll MAXM = 4e5 + 7;
const int MOD = 1e9 + 7;
const double eps = 1e-7;
struct Point
{
double x, y, z;
} P[MAXN];
double dis(Point a, Point b)
{
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) + (a.z - b.z) * (a.z - b.z));
}
int n;
double ans = INF;
double solve()
{
double Statr_T = 1000000;
double t = Statr_T;
double rate = 0.99;
Point now = {0, 0, 0};
int mxgo = 0;
double mxlen = dis(now, P[mxgo]);
while (t > eps)
{
double pre = dis(now, P[mxgo]);
for (int i = 0; i < n; i++)
{
if (dis(now, P[i]) > dis(now, P[mxgo]))
mxgo = i;
}
double nxtx = now.x + (P[mxgo].x - now.x) * t * rand() / RAND_MAX / Statr_T;
double nxty = now.y + (P[mxgo].y - now.y) * t * rand() / RAND_MAX / Statr_T;
double nxtz = now.z + (P[mxgo].z - now.z) * t * rand() / RAND_MAX / Statr_T;
double maxx = 0;
Point nxt = {nxtx, nxty, nxtz};
for (int i = 0; i < n; i++)
maxx = max(maxx, dis(P[i], nxt));
double delta = pre - maxx;
if (delta < 0)
now = nxt;
else if (exp(delta / t) > 1.0 * rand() / RAND_MAX)
now = nxt;
ans = min(ans, maxx);
t *= rate;
}
return ans;
}
int main()
{
srand(time(NULL));
while (~scanf("%d", &n) && n)
{
ans = INF;
for (int i = 0; i < n; i++)
scanf("%lf%lf%lf", &P[i].x, &P[i].y, &P[i].z);
for (int i = 1; i <= 10; i++)
solve();
printf("%.8f
", ans);
}
return 0;
}
三分版
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/trie_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
// freopen("k.in", "r", stdin);
// freopen("k.out", "w", stdout);
// clock_t c1 = clock();
// std::cerr << "Time:" << clock() - c1 <<"ms" << std::endl;
//#pragma comment(linker, "/STACK:1024000000,1024000000")
mt19937 rnd(time(NULL));
#define de(a) cout << #a << " = " << a << endl
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define per(i, a, n) for (int i = n; i >= a; i--)
#define ls ((x) << 1)
#define rs ((x) << 1 | 1)
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<char, char> PCC;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
#define inf 0x3f3f3f3f
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll MAXN = 2e5 + 7;
const ll MAXM = 4e5 + 7;
const int MOD = 1e9 + 7;
const double eps = 1e-8;
struct Point
{
double x, y, z;
} P[MAXN];
int n;
double ans = INF;
double dis(Point a, Point b) { return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) + (a.z - b.z) * (a.z - b.z)); }
double check(Point x)
{
double ret = 0;
for (int i = 1; i <= n; i++)
ret = max(ret, dis(P[i], x));
return ret;
}
Point solve(Point now, int op) //x-1,y-2,z-3
{
double l = -100000, r = 100000;
Point nodel = now, noder = now;
while (r - l > eps)
{
double mid1 = l + (r - l) / 3;
double mid2 = r - (r - l) / 3;
if (op == 1)
nodel.x = mid1, noder.x = mid2;
else if (op == 2)
nodel.y = mid1, noder.y = mid2;
else
nodel.z = mid1, noder.z = mid2;
if (op != 3)
{
nodel = solve(nodel, op + 1);
noder = solve(noder, op + 1);
}
if (check(nodel) > check(noder))
l = mid1;
else
r = mid2;
}
return noder;
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%lf%lf%lf", &P[i].x, &P[i].y, &P[i].z);
Point now = {0, 0, 0};
now = solve(now, 1);
printf("%.10f
", check(now));
return 0;
}