Problem Specification Value
Time Limit 1 Sec
Memory Limit 162 MB
Submit 4156
Solved 2183

Description

有一个球形空间产生器能够在 n 维空间中产生一个坚硬的球体. 现在, 你被困在了这个 n 维球体中, 你只知道球面上 n+1 个点的坐标, 你需要以最快的速度确定这个 n 维球体的球心坐标, 以便于摧毁这个球形空间产生器.

Input

第一行是一个整数 n (1<=N=10). 接下来的 n+1 行, 每行有 n 个实数, 表示球面上一点的 n 维坐标. 每一个实数精确到小数点后 6 位, 且其绝对值都不超过 20000.

Output

有且只有一行, 依次给出球心的 n 维坐标 (n 个实数), 两个实数之间用一个空格隔开. 每个实数精确到小数点后 3 位. 数据保证有解. 你的答案必须和标准输出一模一样才能够得分.

Sample Input

2
0.0 0.0
-1.0 1.0
1.0 0.0

Sample Output

0.500 1.500

HINT

提示: 给出两个定义: 1、球心: 到球面上任意一点距离都相等的点. 2、距离: 设两个 n 为空间上的点 A, B 的坐标为 (a1, a2,. ...... , an), (b1, b2,. ...... , bn), 则 AB 的距离定义为: dist=sqrt ((a1-b1) ^2+(a2-b2) ^2+...... +(an-bn) ^2)

Source

花了很大功夫写了两个版本, 一个是让人写到吐的模拟退火, 另一个是相对友善的高斯消元法. 模拟 退火调了很久很久但是还有许多 BUG, 不过最后还是用高斯消元法 AC 了.


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>

using namespace std;
typedef long double lf;
#define sqr(____x) ((____x) * (____x))
const int maxn = 20;

int n;
lf  coords[maxn][maxn]; // Actual coordinates
lf  mat[maxn][maxn]; // The matrix of linear equations
lf  res[maxn]; // The actual results

int main(int argc, char** argv)
{
    // Read-in data
    scanf("%d", &n);
    for (int i = 0; i <= n; i++)
        for (int j = 1; j <= n; j++)
            scanf("%Lf", &coords[i][j]);
    // Pre-process coords to create matrix
    // 2x(a_2-a_1) + 2y(b_2-b_1)=a_1^2+b_1^2-a_2^2-b_2^2
    for (int i = 1; i <= n; i++) { // Iterate through a_1, 2, 3...
        for (int j = 1; j <= n; j++) // Iterate through x, y, z...
            mat[i][j] = 2.0 * (coords[i][j] - coords[i - 1][j]);
        // Calculate final coefficient
        mat[i][n + 1] = 0.0;
        for (int j = 1; j <= n; j++)
            mat[i][n + 1] += sqr(coords[i - 1][j]) - sqr(coords[i][j]);
    }
    // Calculate matrix using Gaussian Elimination
    // Convert matrix to echelon form
    for (int i = 1; i <= n - 1; i++) { // The equation to be examined
        // To ensure that there's no zero on this particular position
        if (mat[i][i] == 0) {
            // Search through the entire matrix in hope of finding one
            int found = 0;
            for (int j = 1; j <= n; j++)
                if (mat[j][i] != 0)
                    found = j;
            if (!found)
                continue; // We don't need this after all
            // Copying the specific row and add to this row
            for (int j = 1; j <= n + 1; j++)
                mat[i][j] += mat[found][j];
        }
        // Now to solve the elimination
        for (int j = i + 1; j <= n; j++) { // The equation to be eliminated
            lf  elim = - mat[j][i] / mat[i][i];
            for (int k = 1; k <= n + 1; k++)
                mat[j][k] += elim * mat[i][k]; // Eliminate row
            mat[j][i] = 0.0; // Ensure clearness
        }
    }
    // Process echelon matrix to get answers
    for (int i = n; i >= 1; i--) {
        // Take in known values
        for (int j = i + 1; j <= n; j++) {
            mat[i][n + 1] -= mat[i][j] * res[j];
            mat[i][j] = 0.0;
        }
        // Resize this value
        mat[i][n + 1] /= mat[i][i];
        mat[i][i] = 1.0;
        // Upload to final result table
        res[i] = mat[i][n + 1];
    }
    // Print values
    for (int i = 1; i < n; i++)
        printf("%.3Lf ", - res[i]);
    printf("%.3Lf\n", - res[n]); // Or you will get Presentation Error~ 233
    return 0;
}

这就是写吐了的模拟退火----不要借鉴这份代码, 如果它遇到 x-y 比例严重失调的图形会崩掉


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>

using namespace std;
typedef long double lf;
#define sqr(____x) ((____x) * (____x))
const int maxn = 20, maxm = 1010;

int n, spawns = 1, iterts = 32;
lf  xa[maxn][maxn]; // index, dimension
lf  mx_x[maxn], mn_x[maxn]; // dimension, representing extreme values
lf  spx[maxn][maxn]; // spawns: index, dimension
lf  spv[maxn]; // spawns: the current entropy
lf  mx_d, mn_d;
lf  delta, epsilon = 1.0e-6;

lf  calc_entropy(lf* arrx)
{
    lf  val[maxn], sum = 0.0;
    for (int i = 0; i <= n; i++) {
        val[i] = 0.0;
        for (int j = 1; j <= n; j++)
            val[i] += sqr(xa[i][j] - arrx[j]);
        sum += val[i];
    }
    sum /= (lf)(n + 1); // Now sum becomes average / mean
    for (int i = 0; i <= n; i++)
        val[i] = sqr(val[i] - sum);
    sum = 0.0;
    for (int i = 0; i <= n; i++)
        sum += val[i]; // The sum of it's squared distinction
    sum /= (lf)n; // The final result;
    return sum;
}

lf  myrand(lf range)
{
    return rand() * range * 2.0 / RAND_MAX - range;
}

lf  myrand(lf range_l, lf range_r)
{
    return rand() * (range_r - range_l) / RAND_MAX + range_l;
}

lf  center[maxn]; // Pre-processing for precision

int main()
{
    scanf("%d", &n);
    // Set extreme values
    for (int j = 1; j <= n; j++) {
        mx_x[j] = -40000.0;
        mn_x[j] = 40000.0;
    }
    mx_d = 0.0;
    mn_d = 80000.0;
    // Input known coordinates
    for (int i = 0; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            scanf("%Lf", &xa[i][j]);
            mx_x[j] = max(mx_x[j], xa[i][j]);
            mn_x[j] = min(mn_x[j], xa[i][j]);
            center[j] += xa[i][j];
        }
    // Pre-processing graph
    for (int j = 1; j <= n; j++) {
        mx_d = max(mx_d, mx_x[j] - mn_x[j]);
        mn_d = min(mx_d, mx_x[j] - mn_x[j]);
        // Processing side-slipping
        center[j] /= (lf)(n + 1);
        for (int i = 0; i <= n; i++)
            xa[i][j] -= center[j];
        mx_x[j] -= center[j];
        mn_x[j] -= center[j];
    }
    if (mn_d < 1.0)
        epsilon *= mn_d; // .*
    else
        epsilon /= mn_d;
    for (int j = 1; j <= n; j++) {
        for (int i = 0; i <= n; i++)
            xa[i][j] /= mx_d;
        mx_x[j] /= mx_d;
        mn_x[j] /= mx_d;
    }
    // Defining initial precision
    delta = 20000.0;
    // Spawning the initial points
    for (int k = 1; k <= spawns; k++)
        for (int i = 1; i <= n; i++)
            spx[k][i] = myrand(mn_x[i], mx_x[i]);
    for (int k = 1; k <= spawns; k++)
        spv[k] = 8.9e10;
    // Simulated annealing
    while (delta > epsilon) {
        for (int k = 1; k <= spawns; k++) {
            lf  tstx[maxn]; // The sub-routines of this spawn
            lf  best = spv[k];
            // Iterating children on the tree
            for (int i = 1; i <= iterts; i++) {
                lf  nwx[maxn];
                // Generating new node
                for (int j = 1; j <= n; j++)
                    nwx[j] = spx[k][j] + myrand(delta);
                // calculating entropy
                lf  curval = calc_entropy(nwx);
                // cout << curval << endl;
                // If not even better than the original, forget it
                if (curval >= best) continue;
                // Then we'll copy it to the temporary storage
                for (int j = 1; j <= n; j++)
                    tstx[j] = nwx[j];
                best = curval;
            }
            // Done spawning, we shall look over whether to update this spawn
            if (best >= spv[k]) continue;
            // That was nothing happened, now it's getting better!
            for (int j = 1; j <= n; j++)
                spx[k][j] = tstx[j];
            spv[k] = best;
        }
        if (delta <= 100 || spv[1] > 10.0)
            delta *= 0.7071; // .*
    }
    // Generating average values
    lf  avr[maxn];
    for (int j = 1; j <= n; avr[j] = 0.0, j++);
    for (int i = 1; i <= spawns; i++)
        for (int j = 1; j <= n; avr[j] += spx[i][j], j++);
    for (int j = 1; j <= n; avr[j] /= (lf)spawns, j++);
    // Post-processing values
    for (int j = 1; j <= n; j++) {
        avr[j] *= mx_d; // .*
        avr[j] += center[j];
        if (avr[j] > -0.001 && avr[j] < 0.000)
            avr[j] = 0.0;
    }
    // Outputting the result
    for (int i = 1; i <= n; i++)
        printf("%.3Lf ", avr[i]);
    return 0;
}
from pydatagen import *
n = randrange(1, 11)
printf('%d \n' % n)
for i in range(0, n + 1):
    for j in range(0, n):
        out = randrange(-5000000, 5000000) * 0.001
        printf('%.3f ' % out)
    printf('\n')
fclose()