POJ 1914 - Cramer's Rule

http://poj.org/problem?id=1914

概要

3 * 3 の行列について，det(A) を

のように定める．

A の i 列目を b で置き換えたものを A_i とすると，方程式 Ax = b は det(A) != 0 のとき唯一の解 x_i = det(A_i) を持つことが知られている．

det(A_1), det(A_2), det(A_3), det(A) を答え，唯一の解を持つ場合はその解を，持たない場合は「No unique solution」と出力する．

制約

• すべての数は区間 [-1000, 1000] の整数

解法

やるだけ．計算結果が int の範囲に収まらないケースがあることに注意…

 1 #include <cstdio>
 2 #include <vector>
 3 #include <cmath>
 4 using namespace std;
 5 
 6 long long det(const long long a[3][3])
 7 {
 8   long long r = 0LL;
 9   for (int i = 0; i < 3; i++) {
10     const int j = (i+1) % 3;
11     const int k = (j+1) % 3;
12     r += a[0][i]*(a[1][j]*a[2][k] - a[1][k]*a[2][j]);
13   }
14   return r;
15 }
16 
17 int main()
18 {
19   int T;
20   scanf("%d", &T);
21   while (T-- > 0) {
22     long long a[3][3];
23     long long b[3];
24     for (int i = 0; i < 3; i++) {
25       for (int j = 0; j < 3; j++) {
26         scanf("%lld", &a[i][j]);
27       }
28       scanf("%lld", &b[i]);
29     }
30 
31     long long d[3];
32     for (int i = 0; i < 3; i++) {
33       for (int j = 0; j < 3; j++) {
34         swap(a[j][i], b[j]);
35       }
36       d[i] = det(a);
37       printf("%lld ", d[i]);
38       for (int j = 0; j < 3; j++) {
39         swap(a[j][i], b[j]);
40       }
41     }
42     const long long e = det(a);
43     printf("%lld\n", e);
44     if (e == 0LL) {
45       puts("No unique solution");
46     } else {
47       printf("Unique solution:");
48       for (int i = 0; i < 3; i++) {
49         double f = double(d[i]) / e;
50         if (fabs(f) < 1e-4) {
51           f = 0.000;
52         }
53         printf(" %.3f", f);
54       }
55       putchar('\n');
56     }
57     putchar('\n');
58   }
59   return 0;
60 }