题意:给出一个点到12个点的距离,求这个点的坐标。(坐标维数:11)
题目链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4835
——>>因为一定有解,所以转化为线性方程组后直接高斯消元。(训练时我们队FA~激动)
#include <cstdio> #include <cmath> #include <algorithm> #include <cstring> using namespace std; const int maxn = 13; typedef double Matrix[maxn][maxn]; void gause_elimination(Matrix A, int n) { int i, j, k, r; for(i = 0; i < n; i++) { r = i; for(j = i+1; j < n; j++) if(fabs(A[j][i]) > fabs(A[r][i])) r = j; if(r != i) for(j = 0; j <= n; j++) swap(A[r][j], A[i][j]); for(k = i+1; k < n; k++) { for(j = n; j >= i; j--) A[k][j] -= A[k][i] / A[i][i] * A[i][j]; } } for(i = n-1; i >= 0; i--) { for(j = i+1; j < n; j++) A[i][n] -= A[j][n] * A[i][j]; A[i][n] /= A[i][i]; } } int main() { int T, i, j, k; scanf("%d", &T); Matrix a, A; while(T--) { for(i = 0; i < 12; i++) for(j = 0; j < 12; j++) scanf("%lf", &a[i][j]); memset(A, 0, sizeof(A)); for(i = 0; i < 11; i++) { for(j = 0; j < 11 ; j++) { A[i][j] = a[i][j] - a[i+1][j]; } A[i][11] = a[i+1][11] * a[i+1][11] - a[i][11] * a[i][11]; for(k = 0; k < 11; k++) A[i][11] += a[i][k] * a[i][k] - a[i+1][k] * a[i+1][k]; A[i][11] /= 2; } gause_elimination(A, 11); for(i = 0;i < 10; i++) printf("%.2lf ", A[i][11]); printf("%.2lf\n", A[10][11]); } return 0; }