2016 UESTC Training for Math G – 完美点集 解方程

Source

2016 UESTC Training for Math

My Solution

解方程

n+1个点中任意n个点也满足题目的条件

可从n-1维n个点递推

故可以从n个点递推到第n+1个点

第1个点 (defaultdist, 0.0, 0.0, ......, 0.0)

第2个点 (0.0, defaultdist, 0.0，......, 0.0)

..     ...................................

..     ...................................

第n个点 (0.0, 0.0, ............,defaultdist)

这就是这个n+1个点中显然有的n个点， 其中 defdist = sqrt(2)/2.0

然后根据对称性， 设(x, x, ......, x)

然后列方程  (x - defaultdist)^2 + (n-1) x^2 = 1;

n*x^2 + 2*defaultdist*x - defaultdist^2 = 1;

n*x^2 - sqrt(2)*x - 1/2 = 0;

用公式求得一个解就好了

复杂度 O(n^2) 打印结果用了O(n^2), 计算O(1)

#include 
#include 
#include 
using namespace std;

int main()
{
    int n;
    double defdist = sqrt(2)/2.0;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(j == 1){
                if(i == j) printf("%.12f", defdist);
                else printf("0.0");
            }
            else{
                if(i == j) printf(" %.12f", defdist);
                else printf(" 0.0");
            }
        }
        printf("n");
    }
    double x = (sqrt(2) + sqrt(2 + 2*n))/(2*n);
    for(int i = 1; i <= n; i++){
        if(i == 1) printf("%.12f", x);
        else printf(" %.12f", x);
    }
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx